C Merge Sort

Summary: in this tutorial, you will learn about the merge sort algorithm and how to implement it in C.

Introduction to the merge sort algorithm

C merge sort

The merge sort works based on divide-and-conquer strategy as follows:

  1. First, we divide the unsorted list into n sub-lists  Each sub-list contains 1 element, a list with 1 element is considered ordered or sorted.
  2. Second, we merge sub-lists repeatedly to make new sub-lists until there is only one sub-list remaining. This sub-list is the final sorted list.

The complexity of the merge sort algorithm is O(NlogN) where N is the number of elements to sort.

For example, to sort a list of integers 5,6,3,1,7,8,2,4 we do it as illustrated in the picture.

C merge sort implementation

The following program demonstrates how to implement the merge sort in C. Notice the recursion technique is used.

#include <stdio.h> #include <stdlib.h> #define SIZE 8 void merge(int a[], int tmp[], int left, int mid, int right); void msort(int a[], int tmp[], int left, int right); void merge_sort(int a[], int tmp[], const int size); void display(int a[],const int size); int main() { int a[SIZE] = {5,6,3,1,7,8,2,4}; int tmp[SIZE]; printf("--- C Merge Sort Demonstration --- \n"); printf("Array before sorting:\n"); display(a,SIZE); merge_sort(a, tmp, SIZE); printf("Array after sorting:\n"); display(a,SIZE); return 0; } void merge_sort(int a[], int tmp[], const int size) { msort(a, tmp, 0, size - 1); } void msort(int a[], int tmp[], int left, int right) { int mid; if (right > left) { mid = (right + left) / 2; msort(a, tmp, left, mid); msort(a, tmp, mid + 1, right); merge(a, tmp, left, mid + 1, right); } } void merge(int a[], int tmp[], int left, int mid, int right) { int i, left_end, count, tmp_pos; left_end = mid - 1; tmp_pos = left; count = right - left + 1; while ((left <= left_end) && (mid <= right)) { if (a[left] <= a[mid]) { tmp[tmp_pos] = a[left]; tmp_pos = tmp_pos + 1; left = left +1; } else { tmp[tmp_pos] = a[mid]; tmp_pos = tmp_pos + 1; mid = mid + 1; } } while (left <= left_end) { tmp[tmp_pos] = a[left]; left = left + 1; tmp_pos = tmp_pos + 1; } while (mid <= right) { tmp[tmp_pos] = a[mid]; mid = mid + 1; tmp_pos = tmp_pos + 1; } for (i = 0; i <= count; i++) { a[right] = tmp[right]; right = right - 1; } } void display(int a[],const int size) { int i; for(i = 0; i < size; i++) printf("%d ",a[i]); printf("\n"); }
Code language: C++ (cpp)

The output of the program is as follows:

--- C Merge Sort Demonstration --- Array before sorting: 5 6 3 1 7 8 2 4 Array after sorting: 1 2 3 4 5 6 7 8
Code language: C++ (cpp)

In this tutorial, we have introduced you the merge sort algorithm and shown you how to implement it in C.

Was this tutorial helpful ?