Merge sort in C is a divide and conquer algorithm usually used to sort an array. So in this tutorial, the code and algorithm for merge sort in C are discussed to make you understand what is merge sort?

Merge Sort Algorithm

merge sort algorithm in c

  1. Partition the array from the half into left and right sub-arrays.
  2. Repeat step-1 for both left and right sub-arrays, until the subarray contains only one element (one element cannot be partitioned :P).
  3. Merge left and right subarray by sorting the elements into one.
  4. Repeat step-3 until you get all the elements sorted in the final array.

C

Java

Output

Overview of Merge Sort

  • Not an in-place algorithm (requires two extra arrays for splitting into two halves).
  • O(nlogn)-base 2 complexity. We are repeatedly dividing the array.
  • Stable algorithm (No interchange of duplicates values).

We have successfully sorted an array using merge sort which is one of the divide and conquer algorithm. If you have any doubt then comment below. Pencil Programmer will be happy to help.

Leave a Reply

Close Menu