#include <iostream>
using namespace std;
void
merge (int arr[], int low, int middle, int high)
{
int b1Size = middle - low + 1;
int b2Size = high - middle;
int b1[b1Size], b2[b2Size];
cout << "Initialisation of First Half of Array elements: \n";
for (int i = 0; i < b1Size; i++) {
b1[i] = arr[low + i];
cout << b1[i] << " ";
}
cout << "\n\n";
cout << "Initialisation of Second Half of Array elements: \n";;
for (int j = 0; j < b2Size; j++) {
b2[j] = arr[j + middle + 1];
cout << b2[j] << " ";
}
cout << "\n\n";
int i = 0;
int j = 0;
int k = low;
while (i < b1Size && j < b2Size) {
if (b1[i] <= b2[j]) {
arr[k] = b1[i];
i++;
} else {
arr[k] = b2[j];
j++;
}
k++;
}
while (i < b1Size) {
arr[k] = b1[i];
i++;
k++;
}
while (j < b2Size) {
arr[k] = b2[j];
j++;
k++;
}
#if 1 // Debugging
cout << "Middle " << middle << " Array[" << low << "] to Array[" << high << "]\n";
for (int i = low; i <= high; i++) {
cout << arr[i] << " ";
}
cout << "\n\n";
#endif
return;
}
void
mergeSort (int arr[], int low, int high)
{
if (low < high) { // Base Condition
int middle = (high + low - 1)/ 2;
#if 1 // Debugging
cout << "High " << high << " Array[" << low << "] to Array[" << middle << "]\n";
for (int i = low; i <= middle; i++) {
cout << arr[i] << " ";
}
cout << "\n\n";
#endif
mergeSort (arr, low, middle);
#if 1 // Debugging
cout << "Low " << low << " Array[" << middle+1 << "] to Array[" << high << "]\n";
for (int i = middle + 1; i <= high; i++) {
cout << arr[i] << " ";
}
cout << "\n\n";
#endif
mergeSort (arr, middle + 1, high);
#if 1 // Debugging
cout << "Middle " << middle << " Array[" << low << "] to Array[" << high << "]\n";
for (int i = low; i <= high; i++) {
cout << arr[i] << " ";
}
cout << "\n\n";
#endif
merge (arr, low, middle, high);
}
#if 1
cout << "Returned : low " << low << " high " << high << "\n";
cout << "\n ************************** \n";
#endif
return;
}
int main ()
{
int arr[] = { 6, 5, 12, 10, 9, 1 };
int size = sizeof (arr) / sizeof (arr[0]);
cout << "Array elements before sorting: \n";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << "\n ************************** \n";
mergeSort (arr, 0, size-1);
cout << "\n Array elements after sorting: \n";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return 0;
}
