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 sortThe 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 contain 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 picture.

C merge sort implementation

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

The output of the program is as follows:

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