Merge Sort Algorithm - Java, C, and Python Implementation With Examples

Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and Conquer based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.

Merge Sort Working Rule

The concept of Divide and Conquer involves three steps:

  1. Divide the problem into multiple subproblems.
  2. Solve the Sub Problems. The idea is to break down the problem into atomic subproblems, where they are actually solved.
  3. Combine the solutions of the subproblems to find the solution of the actual problem.

So, the merge sort working rule involves the following steps:

  1. Divide the unsorted array into subarray, each containing a single element.
  2. Take adjacent pairs of two single-element array and merge them to form an array of 2 elements.
  3. Repeat the process till a single sorted array is obtained.

An array of Size ā€˜Nā€™ is divided into two parts ā€˜N/2ā€™ size of each. then those arrays are further divided till we reach a single element.

The base case here is reaching one single element. When the base case is hit, we start merging the left part and the right part and we get a sorted array at the end.

Merge sort repeatedly breaks down an array into several subarrays until each subarray consists of a single element and merging those subarrays in a manner that results in a sorted array.

Merge Sort Algorithm Flow

Array = {70,50,30,10,20,40,60}

MergeSort

 

MergeSort

We repeatedly break down the array in two parts, the left part, and the right part. the division takes place from the mid element.

We divide until we reach a single element and then we start combining them to form a Sorted Array.

Merge Sort Implementations

We will implement the merge sort algorithm in Java, C, and Python.

1. Java Implementation

OUTPUT

Merge Sort Algorithm Java Implementation

 

Merge Sort Algorithm Java Implementation

2. C Implementation

OUTPUT

Merge Sort Python Code

 

Merge Sort C Implementation

3. Python Implementation

OUTPUT

Merge Sort Python Code

 

Merge Sort Python Code

Merge Sort Time and Space Complexity

1. Space Complexity

Auxiliary Space: O(n)
Sorting In Place: No
Algorithm : Divide and Conquer

2. Time Complexity

Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.

T(n) = 2T(n/2) + O(n)

The solution of the above recurrence is O(nLogn). The list of size N is divided into a max of Logn parts, and the merging of all sublists into a single list takes O(N) time, the worst-case run time of this algorithm is O(nLogn)

Best Case Time Complexity: O(n*log n)

Worst Case Time Complexity: O(n*log n)

Average Time Complexity: O(n*log n)

The time complexity of MergeSort is O(n*Log n) in all the 3 cases (worst, average and best) as the mergesort always divides the array into two halves and takes linear time to merge two halves.

Further Readings:

By admin

Leave a Reply