Merge sort Data Structure

Merge sort

Merge sort is based on the divide & conquer sorting technique. Merge sort is a very efficient sorting algorithm. The divide & conquer technique was introduced by John Newman in 1945. The divide & conquer is a technique in which a complex list of data is divided into a sub-list, and this list is split until there is only one element left in the list. After that, these sub-lists are sorted, and then all elements are combined. Merge sort is also called a two-way sort.

Complexity table of Merge sort

Complexity Best case Average case Worst case
Time O(nlogn) O(nlogn) O(nlogn)
Space     O(n)

Merge sort algorithm

if BEG < END
set MID = (BEG / END) / 2
MERGE_SORT (ARR, BEG, MID)
MERGE_SORT (ARR, MID + 1, END)
MERGE_SORT (ARR, BEG, MID, END)

Step 1: MERGE (SET I = BEG, J = MID + 1, INDEX = 0) Step 2: Repeat while (I <= MID) and (J<=END)
             if ARR[I] < ARR[J]
             SET TEMP[INDEX] = ARR[I]
             SET I = I + 1
             else
             SET TEMP[INDEX] = ARR[J]
             SET J = J + 1
             //end of if
             SET INDEX = INDEX + 1
             //end of loop
Step 3: [Copy the remaining elements of right sub-array, if any]
            if I > MID
            Repeat while J <= END
            SET TEMP[INDEX] = ARR[J]
            SET INDEX = INDEX + 1, SET J = J + 1
            //end of loop
            [Copy the remaining elements of left sub-array, if any]
                        else
            Repeat while I <= MID
            SET TEMP[INDEX] = ARR[I]
            SET INDEX = INDEX + 1, SET I = I + 1
            //end of loop
            //end of if Step 4: [Copy the contents of TEMP back to ARR] SET K = 0 Step 5: Repeat while K < INDEX
             SET ARR[K] = TEMP[K]
             SET K = K + 1
             //end of loop Step 6: exit  

Merge sort example

Suppose we have the following array, which we have to sort.

11 54 45 65 32 44 91 25

As you know, the whole array is divided into two parts in the merge sort.

This array has 8 elements, and this array will be divided into two arrays. You divide this array until there is only one element remain in it. After this, all elements are compared with each other, and after that, they are sorted and combined.

Merge sort program in C language

 #include <stdio.h>   void mergesort(int a[], int p, int r)   {       int q;       if(p < r)       {           q = (p +   r) / 2;           mergesort(a,   p, q);           mergesort(a,   q+1, r);           merge(a,   p, q, r);       }   }       // function to merge the   subarrays   void merge(int a[], int p, int q, int r)   {       int   b[5];   //same size of a[]       int i, j, k;       k = 0;       i = p;       j = q + 1;       while(i <=   q && j <= r)       {           if(a[i]   < a[j])           {                 b[k++] = a[i++];    // same as   b[k]=a[i]; k++; i++;           }           else           {                 b[k++] = a[j++];           }       }            while(i <=   q)       {           b[k++] =   a[i++];       }            while(j <=   r)       {           b[k++] =   a[j++];       }            for(i=r; i   >= p; i--)       {           a[i] =   b[--k];  // copying back the sorted   list to a[]       }    }       // function to print the array   void printArray(int a[], int size)   {       int i;       for (i=0; i   < size; i++)       {             printf("%d ", a[i]);       }         printf("\n");   }       int main()   {       int arr[] = {11,   54, 45, 65, 32, 44, 91, 25};       int len =   sizeof(arr)/sizeof(arr[0]);           printf("Unsorted   array: \n");         printArray(arr, len);              // calling merge sort       mergesort(arr,   0, len - 1);             printf("\nSorted array: \n");         printArray(arr, len);       return 0;   }        

Output:

Unsorted   array:   11 54 45 65   32 44 91 25   
Sorted   array:   11 25 32 44   45 54 65 91