#include <iostream>
using namespace std;
void mergeSort(int a[], int lowIndex, int highIndex);
void merge(int a[], int lowIndex, int midIndex, int highIndex);
int main(){
int myvec[] = {70, 30, 80, 10, 0, 50, 20, 60, 90, 40};
mergeSort(myvec, 0, 9);
for(int i=0; i<=9; i++){
cout<<myvec[i]<<", ";
}
cout<<endl;
//int midIndex = (0+1)/2+1;
//cout<<endl<<endl<<midIndex<<endl<<endl;
return 0;
}
/*Utilizar mergeSort con los elementos
desde a[lowIndex] - hasta a[highIndex]*/
void mergeSort(int a[], int lowIndex, int highIndex){
if(lowIndex < highIndex){
int midIndex = (lowIndex+highIndex)/2;
//Dividir a[] en dos mitades y
//ordenarlas recursivamente
mergeSort(a, lowIndex, midIndex);
mergeSort(a, midIndex+1, highIndex);
//fusionar las mitades ordenadas
//Se fusiona a[lowIndex ... midIndex] y a[midIndex+1 ... highIndex]
//en a[lowIndex... highIndex]
merge(a, lowIndex, midIndex, highIndex);
}else{
//Caso base: (lowIndex >= highIndex)
return;
}
}
void merge(int a[], int lowIndex, int midIndex, int highIndex){
int n = highIndex-lowIndex+1;
// Arreglo temportal b[] donde se guardan
// Los elementos fusionados
int b[n];
b[n] = {}; // se inicializa en cero
int leftIndex = lowIndex;
int rightIndex = midIndex+1;
int bIndex = 0;
// Fusion normal: cuando ambas mitades tienen
// elementos que no se han fusionado
while(leftIndex<=midIndex && rightIndex<=highIndex){
if(a[leftIndex] <= a[rightIndex]){
b[bIndex++] = a[leftIndex++];
}else{
b[bIndex++] = a[rightIndex++];
}
}
// Los elementos que quedan se copian a b[]
while(leftIndex <= midIndex)
b[bIndex++] = a[leftIndex++];
while(rightIndex <= highIndex)
b[bIndex++] = a[rightIndex++];
// El resultado de la fusion se copia de nuevo a a[]
for(int k=0; k<n; k++){
a[lowIndex+k] = b[k];
}
}
