Merge Sort Algorithm, in another efficient sorting algorithm that divides the input array into two parts and it calls itself recursively for the two parts. Then merges these two sorted parts. It is a Divide and Conquer algorithm. Merge function used to merge two parts of array. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
Merging algorithm function runs by array with left, mid and right indexes, it should be be as given below;
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void my_merge(int array[], int l, int m, int r) { int i, j, k, n1 = m-l+1, n2 = r-m, L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = array[l + i]; // Copy to Left temp for (j = 0; j < n2; j++) R[j] = array[m + 1 + j]; // Copy to Right temp i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { array[k] = L[i]; i++; } else { array[k] = R[j]; j++; } k++; } // Let's copy the final sorted elements of Left & Right while (i < n1) { array[k] = L[i]; i++; k++; } while (j < n2) { array[k] = R[j]; j++; k++; } } |
and my_mergesort() functions runs by array, start and end indexes as below;
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void my_mergesort(int array[], int start, int end) { if (start < end) { int mid = start + (end - start) / 2; my_mergesort(array, start, mid); my_mergesort(array, mid + 1, end); my_merge(array, start, mid, end); } } |
Full code of Merge Sort Algorithm will be as below in C++ Builder Console VCL application.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <vcl.h> #include <tchar.h> #include <stdio.h> #include <windows.h> #pragma hdrstop #pragma argsused void my_merge(int array[], int l, int m, int r) { int i, j, k, n1 = m-l+1, n2 = r-m, L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = array[l + i]; // Copy to Left temp for (j = 0; j < n2; j++) R[j] = array[m + 1 + j]; // Copy to Right temp i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { array[k] = L[i]; i++; } else { array[k] = R[j]; j++; } k++; } // Let's copy the final sorted elements of Left & Right while (i < n1) { array[k] = L[i]; i++; k++; } while (j < n2) { array[k] = R[j]; j++; k++; } } void my_mergesort(int array[], int start, int end) { if (start < end) { int mid = start + (end - start) / 2; my_mergesort(array, start, mid); my_mergesort(array, mid + 1, end); my_merge(array, start, mid, end); } } int _tmain(int argc, _TCHAR* argv[]) { int i,n=5, mat[5] = { 3, 30, 34, 5, 9 }; my_mergesort( mat, 0, n-1); for (i=0; i<n; i++) printf ("%d,",mat[i]); getchar(); return 0; } |
Head over and find out more about building Windows apps with modern C++.
