*Divide*- First the objects are divided into smaller sorting problem, so on till only one object is left to sort.
- Trivial solution when one object is left, Sorted one item is itself.

*Combine*- After this combining start where each sorted array are combined to get a bigger sorted array.
- This is continued till the we get the whole array sorted.

*Strategy*- Lets have all the number in array named a;
- Lets have a macro Num_Elems that returns number of items in array a.
- print_array is a utility function that will print the array items for us.
- Implementing 1, 2, 3 are quite straight forward.
- Lets implement the Divide part of the Merge sort algorithm in divide function.
- To divide the array lets pass the pointer to start of array.
- Start index and End Index
- Hence the prototype will look as follows
- int divide(int *a, int start, int end)
- Combine part of the Merge sort algorithm is implemented in combine function.
- To combine the array lets pass th pointer to start of array.
- NOTE combine always involves combining adjacent array.
- Hence only start, middle and end index are sufficient for combining.
- Hence the prototype will look as follows
- int combine(int *a, int start, int middle, int end)

#include <stdio.h> #include <stdlib.h> #include <limits.h> #define NUM_ELE(a) sizeof(a)/sizeof(a[0]) int divide(int *, int, int); int combine(int *, int, int, int); void print_array(int *, int); int main() { int i; int a[] = {4, 5, 1, 2, 5, 10, 1}; printf("Unsorted Array is - "); print_array(a, NUM_ELE(a)); printf("\n"); divide(a, 0, NUM_ELE(a) - 1); printf("Sorted Array is - "); print_array(a, NUM_ELE(a)); printf("\n"); } int divide(int *a, int start, int end) { int middle; if(start < end) { middle = (start + end) / 2; divide(a, start, middle); divide(a, middle + 1, end); combine(a, start, middle, end); } return 0; } int combine(int *a, int start, int middle, int end) { int *L = malloc(sizeof(int) * (middle - start +1)); int *R = malloc(sizeof(int) * (end - middle)); int i; int i_r, i_l; if( L == NULL || R == NULL) { printf("ERROR: malloc failed, may day !!!\n"); exit(0); } /* Fill in L array */ for(i = 0; i < middle - start + 1; i++) { L[i] = a[start + i]; } L[i] = INT_MAX; /* Marking End of Array */ /* Fill in R array */ for(i = 0; i < end - middle ; i++) { R[i] = a[middle + i + 1]; } R[i] = INT_MAX; /* Marking End of Array */ /* Combine from L and R and place it in a */ i_l = i_r = 0; for(i = start; i <= end; i++) { if(L[i_l] <= R[i_r]) { a[i] = L[i_l++]; }else { a[i] = R[i_r++]; } } free(L); free(R); } void print_array(int *arr, int n) { int i; for(i = 0; i < n; i++) { printf(" %d", arr[i]); } }

Output of the program is

Unsorted Array is - 4 5 1 2 5 10 1 Sorted Array is - 1 1 2 4 5 5 10

## Links

Next Article - C Programming Challenge #05: Sort - merge (without sentinels)Previous Article - C Programming Challenge #03: Sort - selection

All Article - C Programming Challenge

## No comments :

## Post a Comment