#include #include #define N 10 /* merge will combine two arrays into the sorted value */ void merge(int list[], int lower[], int higher[], int left, int right) { //values to increment int i = 0, j = 0, k = 0; //while there are still variables in lower and higher while (i < left && j < right) { //if the value of lower[i] <= higher[j] if (lower[i] <= higher[j]) { //assign value to list[k] list[k] = lower[i]; i++; //move to next value of lower } //value of higher < lower else { //assign value to list[k] list[k] = higher[j]; j++; //move to next value of higher } //increment to next location in list k++; } //move leftover elements of lower into list while (i < left) { list[k] = lower[i]; i++; k++; } //move leftover elements of higher into list while (j < right) { list[k] = higher[j]; j++; k++; } } void mergeSort(int list[], int n) { int i; int lower[N], higher[N]; int left, right; if (n < 2) return; //base case // divide list into two array lower and higher left = n / 2; // the number of elements in lower right = n - left; // the number of elements in higher // move the first n/2 elements to lower for (i = 0; i < left; i++) { lower[i] = list[i]; } // move the rest to higher for (i = 0; i < right; i++) { higher[i] = list[i + left]; } // recursive calls mergeSort(lower, left); mergeSort(higher, right); // conquer merge(list, lower, higher, left, right); } int main(void) { int B[N] = {9, 5, 7, 1, 3, 2, 0, 4, 8, 6}; int i = 0; //print unsorted array std::cout << "************** Result **************" << std::endl; std::cout << "The input array is: " << std::endl; for (i = 0; i < N; i++) { std::cout << B[i] << " "; } std::cout << std::endl; // call merge sort mergeSort(B, N); /* print the sorted array */ std::cout << "The sorted array is: " << std::endl; for (i = 0; i < N; i++) { std::cout << B[i] << " "; } std::cout << std::endl; return 0; }