Merge sort algorithm in C with Program sample

: 9612

Last Updated : 04/01/2023

Posted By :- Vinnu

Merge sort is a sorting algorithm that uses the divide, conquer, and combine algorithmic paradigm. Divide means partitioning the n-element array to be sorted into two sub-arrays of n/2 elements. If A is an array containing zero or one element, then it is already sorted. However, if there are more elements in the array, divide A into two sub-arrays, A1 and A2 , each containing about half of the elements of A.

Conquer means sorting the two sub-arrays recursively using merge sort.

Combine means merging the two sorted sub-arrays of size n/2 to produce the sorted array of n elements.

Merge sort algorithm focuses on two main concepts to improve its performance (running time):

A smaller list takes fewer steps and thus less time to sort than a large list.
As a number of steps are relatively less, thus less time is needed to create a sorted list from two sorted lists rather than creating it using two unsorted lists.

The basic steps of a merge sort algorithm are as follows:

If the array is of length 0 or 1, then it is already sorted.
Otherwise, divide the unsorted array into two sub-arrays of about half the size.
Use merge sort algorithm recursively to sort each sub-array.
Merge the two sub-arrays to form a single sorted list.

Merge sort algorithm in C

The merge sort algorithm uses a function merge which combines the sub-arrays to form a sorted array. While the merge sort algorithm recursively divides the list into smaller lists, the merge algorithm conquers the list to sort the elements in individual lists. Finally, the smaller lists are merged to form one list.

Let's consider two functions, one is merge function which combines the sub-arrays and another function MERGE which divides the list into smaller units, here are the two functions algorithm.

// MERGE_SORT(ARR, BEG, END)


Step 1: IF BEG < END
        SET MID = (BEG + END)/2
        CALL MERGE_SORT (ARR, BEG, MID)
        CALL MERGE_SORT (ARR, MID+1, END)
        MERGE (ARR, BEG, MID, END)
        [END OF IF]
Step 2: END

Another function algorithm

// MERGE (ARR, BEG, MID, END)
Step 1: [INITIALIZE] SETI= BEG,J= MID+1, INDEX =
Step 2: Repeat while (I <= MID) AND (J<=END)
         IF ARR[I] < ARR[J]
           SET TEMP[INDEX] = ARR[I]
           SETI=I+1
         ELSE
           SET TEMP[INDEX] = ARR[J]
           SETJ=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 whileJ<= END
             SET TEMP[INDEX] = ARR[J]
             SET INDEX = INDEX+1, SETJ=J+1
          [END OF LOOP]
       [Copy the remaining elements of left sub-array, if any]
        ELSE
           Repeat whileI<= MID
             SET TEMP[INDEX] = ARR[I]
             SET INDEX = INDEX+1, SETI=I+1
           [END OF LOOP]
        [END OF IF]
Step 4: [Copy the contents of TEMP back to ARR] SET K=
Step 5: Repeat whileK< INDEX
          SET ARR[K] = TEMP[K]
          SETK=K+1
        [END OF LOOP]
Step 6: END

The running time of merge sort in the average case and the worst case can be given as O(n log n). Although merge sort has an optimal time complexity, it needs an additional space of O(n) for the temporary array TEMP.

Merge sort program in C

#include <stdio.h> 
#include <conio.h>

#define size 100

void merge(int a[], int, int, int);
void merge_sort(int a[], int, int);

void main() {
  int arr[size], i, n;
  printf("\n Enter the number of elements in the array : ");
  scanf("%d", & n);
  printf("\n Enter the elements of the array: ");
  for (i = 0; i < n; i++) {
    scanf("%d", & arr[i]);
  }
  merge_sort(arr, 0, n - 1);
  printf("\n The sorted array is: \n");
  for (i = 0; i < n; i++)
    printf(" %d\t", arr[i]);
  getch();
}


void merge(int arr[], int beg, int mid, int end) {
  int i = beg, j = mid + 1, index = beg, temp[size], k;
  while ((i <= mid) && (j <= end)) {
    if (arr[i] < arr[j]) {
      temp[index] = arr[i];
      i++;
    } else {
      temp[index] = arr[j];
      j++;
    }
    index++;
  }
  if (i > mid) {
    while (j <= end) {
      temp[index] = arr[j];
      j++;
      index++;
    }
  } else {
    while (i <= mid) {
      temp[index] = arr[i];
      i++;
      index++;
    }
  }
  for (k = beg; k < index; k++)
    arr[k] = temp[k];
}


void merge_sort(int arr[], int beg, int end) {
  int mid;
  if (beg < end) {
    mid = (beg + end) / 2;
    merge_sort(arr, beg, mid);
    merge_sort(arr, mid + 1, end);
    merge(arr, beg, mid, end);
  }
}

When executing the above code online here https://onlinegdb.com/rkjAURCxX gives output

 Enter the number of elements in the array : 5

 Enter the elements of the array: 11 2 3 99 4

 The sorted array is: 
 2	 3	 4	 11	 99

In the above code, we are first breaking or dividing arrays using merge_sort method and then using merge(arr, beg, mid, end); to combine sorted array elements.