Merge Sort

Introduction

Merge sort is one of the famous sorting algorithms. Merge sort works on simple premise of divide and conquer. In this blog we will discuss about Merge sort and get a brief idea about notion of divide and conquer.

Divide and Conquer

Divide and conquer is an approach where we divide a large problem into smaller, easier to solve sub problems. Results of these smaller sub problems can be combined to give the final answer.

  1. Conquer: Conquer sub-problems by solving them recursively.
  2. Combine: Combine the answers of these sub problem and merge them to get the answer of original problem
An algorithm devised by using divide and conquer approach

Merge Sort

The main idea behind merge sort is to divide the array or list to be sorted into smaller sub arrays or sub lists. Here we sort and combine these sub lists or sub arrays recursively to get the sorted array or list for the given original unsorted list or array.

An example of merge sort algorithm

Divide:

Let mid be the middle point of the array then we can split our original array Arr[start , last] into two smaller sub arrays that is Arr[start , mid] and Arr[mid+1 , last].

Conquer:

In this step, we will sort the two subarrays Arr[start , mid] and Arr[mid+1 , last] if best case is reached. If not ,then we again divide both these subarrays and try to sort them.

Combine:

When we get our two sorted subarrays Arr[start,mid] and Arr[mid+1,last] from the conquer step , then we can combine both these sorted arrays to get the result which is sorted array Arr[start , last].

Implementation of Merge Sort Algorithm:

We will use two function Sort() and Merge(). Sort function will divide the array into two half arrays till we reach a stage when subarrays have only one element i.e. (start==last). After this Merge function starts running and combines these sorted sub arrays into a larger sorted array. This will continue till the whole array is merged.

Sort function code:

Sort (int Arr[], int start, int last) {

Code for merge function:

void merge (int Arr[], int start, int last, int mid)

Explanation of Merge function:

  1. Create copies of the subarrays temp_1 -> Arr[start,mid] and temp_2 -> Arr[mid+1,last].
  2. Create three pointers i,j and count .
  3. i maintains current index of temp_1.
  4. j maintains current index of temp_2 and count maintains current index of Arr[start,last].
  5. Now looping will continue till it reaches end of temp_1 or temp_2.
  6. In each iteration of loop, we pick the smaller among elements of temp_1 and temp_2 and place it in correct position.
  7. When we come out of loop (elements of either temp_1 or temp_2 have run out) pick up the remaining elements and put them in Arr[start,last].
Let us take sorted sub arrays Arr1 -> Arr[0,2] and Arr2 -> Arr[3,5]

Step 1:

create copies of sorted sub arrays to be merged.

Step 2:

Maintain index of sub-arrays and main array

index of sub-arrays and main array

Step 3:

Now looping will continue till it reaches either of temp_1 or temp_2. In each iteration of loop, we pick the smaller among elements of temp_1 and temp_2 and place it in correct position.

Step 4:

When it comes out of loop (elements of either temp_1 or temp_2 have run out) pick up the remaining elements and put them in Arr[start,last]

Complexity of Merge Sort:

Using Sort() function we are dividing our array into two subarrays and we continue to do this with each subarray till best case is reached. Hence complexity of merge function is O(log n). We are also merging these sorted sub arrays using merge function which has a complexity of O(n). Hence complexity of merge sort algorithm is O((log n) x n) or O(n log n)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store