C Program To Perform Merge Sort

Merge Sort is an external sorting algorithm and it is the best example for divide and conquer strategy.  It divides the problem into smaller units and solve it recursively.

                                   ----------------------
level 0                         | 40 | 20 | 30 | 10 |
                                   ----------------------
                                   /                         \
                             -----------                -----------
level 1                   | 40 | 20 |               | 30 | 10 |
                             -----------                 ----------
                             /           \                  /          \
                         -------    -------          -------     -------
level 2               |  40  |   |  20 |         | 30  |    |  10  |
                         -------     ------           ------      -------
                           \               /              \                 /
                          ---------------              ---------------
level 3                |  20  |  40   |            |  10   |   30 |
                          ---------------              ---------------
                                   \                            /
                                     ----------------------
level 4                           | 10 | 20 | 30 | 40 |
                                     ----------------------

In the above example, we have totally five levels.  Level 0 to 2 involves dividing phase and the level 3 and 4 involves conquering phase.  Let us see how to merge two sorted sublists.

                  --------------                        --------------                  
Sublist 1:    | 20   |  40 |       Sublist 2:  | 10  | 30  |    
                  ---------------                       -------------                  
                     ^                                        ^                                   
                   slptr1                                  slptr2                  

             -------------------------
Output: |       |      |     |     |
             -------------------------
                ^
              optr

Above are two sublists and an output array.  slptr1, slptr2 and optr are the counters corresponding to sublist1, sublist 2 and the output array.

sublist1[slptr1] is greater than sublist2[slptr2] (ie. 20 > 10).  So, 40 is added to the output array.  Increment slptr2 and optr.

               --------------                        --------------                  
Sublist 1: | 20   |  40 |       Sublist 2:  | 10  | 30  |    
               --------------                        -------------        
                    ^                                               ^                                
                  slptr1                                        slptr2         

             -----------------------
Output: | 10 |     |     |     |
             -----------------------
                       ^
                     optr

sublist1[slptr1] is lesser than sublist2[slptr2](ie. 20 < 30).  So, 20 is added to the output array.  Increment slptr1 and optr.

                --------------                        -------------      
Sublist 1:  | 20   |  40 |       Sublist 2:  | 10  | 30  |    
                --------------                        -------------     
                              ^                                      ^          
                            slptr1                               slptr2       

             ------------------------
Output: | 10  | 20 |     |      |
             ------------------------
                                ^
                             optr

sublist1[slptr1] is greater than sublist2[slptr2](ie. 40 > 30).  So, 30 is added to the output array.  Increment slptr2 and optr.

               --------------                      --------------    
Sublist 1: | 20   |  40 |       Sublist 2:  | 10  | 30  |   
               --------------                      --------------    
                             ^                                            ^ 
                           slptr1                                       slptr2 

             -----------------------
Output: | 10  | 20 | 30 |     |
             -----------------------
                                      ^
                                    optr
Add the unprocessed element in sublist1 to output array and increment slptr1.

                --------------                        --------------     
Sublist 1:  | 20   |  40 |       Sublist 2:  | 10  | 30  | 
                --------------                         -------------    
                                    ^                                       ^  
                                  slptr1                                 slptr2

             -----------------------
Output: | 10  | 20 | 30 | 40|
             ------------------------
                                            ^
                                          optr
So, all the elements in both the sub-lists are processed and the elements in the output array are sorted.

See Also:
C Program To Perform Insertion Sort
C Program To Perform Shell Sort
C Program To Perform Bubble Sort
C Program To Perform Quick Sort
C Program To Perform Radix Sort
C Program To Perform Selection Sort
C Program To Perform Heap Sort
C Program To Perform Merge Sort
C Program To Perform External Sorting
C Program To Perform Sorting Using Binary Search Tree


Example Program To Perform Merge Sort:

---

  #include <stdio.h>
  #include <stdlib.h>

  void merge(int *data, int *tmpdata, int leftPos, int lend, int rend) {
        int num, rightPos, i, tmpIndex;
        tmpIndex = leftPos;
        rightPos = lend + 1;
        num = rend -leftPos + 1;

        while (leftPos <= lend && rightPos <= rend) {
                /*
                 * if the data in leftsub array is greater than
                 * data in right subarray, then add the data
                 * right subarray to output.  Otherwise, viseversa.
                 */
                if (data[leftPos] <= data[rightPos])
                        tmpdata[tmpIndex++] = data[leftPos++];
                else
                        tmpdata[tmpIndex++] = data[rightPos++];
        }
        /* add the unprocessed data to output */
        while(leftPos <= lend)
                tmpdata[tmpIndex++] = data[leftPos++];
        while(rightPos <= rend)
                tmpdata[tmpIndex++] = data[rightPos++];
        /* copy the temporary output to original output */
        for (i = 0; i < num; i++, rend--)
                data[rend] = tmpdata[rend];
  }

  void msort(int *data, int *tmpdata, int left, int right) {

        int mid;

        if (left < right) {

                mid = (left + right) / 2;

                /* dividing phase */

                msort(data, tmpdata, left, mid);

                msort(data, tmpdata, mid+1, right);

                /* conquering phase */

                merge(data, tmpdata, left, mid, right);

        }

  }

  void mergeSort(int *data, int n) {

        int *tmpdata;

        /* temporary buffer to store output */

        tmpdata = (int *)malloc(sizeof (int) * n);

        msort(data, tmpdata, 0, n-1);

        free(tmpdata);

  }

  int main() {

        int n, *data, i;

        printf("Enter ur number of entries:");

        scanf("%d", &n);

        data = (int *)malloc(sizeof (int) * n);

        printf("Enter ur inputs:\n");

        for (i = 0; i < n; i++)

                scanf("%d", &data[i]);

        mergeSort(data, n);

        printf("Sorted Data:");

        for (i = 0; i < n; i++)

                printf("%3d", data[i]);

        printf("\n");

        return 0;

  }

  Output: (C Program To Implement Merge Sort)

  jp@jp-VirtualBox:$ ./a.out
  Enter ur number of entries:5
  Enter ur inputs:
  40 20 10 30 50
  Sorted Data: 10 20 30 40 50