Summary: In this tutorial, we will learn what the Merge Sort Algorithm is, how it works, and how to sort an array using the Merge Sort algorithm in C and Java.

Introduction to Merge Sort Algorithm

Merge sort is a divide and conquer algorithm that divides the array repeatedly into equal halves and arrange them accordingly in the merge process.

Here is the visualization of how merge sort works:

Merge sort visualization
Merge Sort Visualization (Source: Wikipedia)

The algorithm first iteratively divides the array into equal halves until each halves reduces to single element.

Then it combines them in the same manner as they were divided in an ordered way.

Merge Sort Algorithm

  1. Partition the array into equal halves.
  2. Repeat step-1 for both left and right partition, until the partition reduces to only one element.
  3. Merge the partitions into the new array in sorted order.
  4. Repeat step-3 until all the partition is merged.

In actual programming, we don’t merge the partitions (sub-arrays) into a new array or list rather we implement the divide and merge process on the original array using recursion.

The base condition of the recursion i.e. start_index<end_index ensures that the recursive divide process stops for each partition if it has only single element.

On backtracking of the recursive calls we sort the array (partitions).

Here is the implementation of the steps in C and Java:

C

Java

Output

In the above program, the recursive function sort() or mergeSort() do the work of dividing the array and the merge() function arranges the elements of the partitions in sorted order.

In the merge function, we use extra two arrays a1 and a2 to store the array values of the left and right partition. We then put theses array values one by one into the original array in an ordered fashion.

Overview of Merge Sort

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

In this tutorial, we learned what merge sort algorithm is, how it works, and how to implement merge sort algorithm to sort an array in C and Java programming languages.

Leave a Reply

13 − twelve =