Merge Sort

Design and Analysis of algorithm

What is merge sort?

Divide and conquer algorithm

How merge sort works ?

For arrays

  1. If there is only one element present, return the element as it is already sorted.
  2. Then list is sorted into halves till it cannot be further divided.
  3. These smaller lists are merged into new lists in sorted way.

For linked lists

  1. If there is only one element or head is null in linked list , return.
  2. If step 1 does not follow then divide the linked list into 2 halves.
  3. After that the 2 halves are sorted.
  4. Then the halves are merged and head pointer is updated using headref(you can take any other variable ).
An example demonstrating merge sort for an array . Source - (
An example demonstrating merge sort for a singly linked list. Source — (


  1. We have to declare left and right variables which will declare the indexes.
  2. Assign left as zero and right as n-1(where n is the number of variables).
  3. Calculate mid by (left + right)/2.
  4. Call function on (left,mid) and (mid+1,rear) and continue till left<right, else return.
  5. Then merge the above subproblems.

Code(for an array)

#include <bits/stdc++.h>
using namespace std;
// We create two subarrays
// First from arr[x..p] and second from arr[p+1..y]
// where x is leftmost index and y is rightmost index
void func(int arr[], int x, int p, int y)
int m = p — x + 1;
int n = y — p;
// Here we are creating temporary arrays as arr1 and arr2
int arr1[m], arr2[n];
//copying data to temporary arrays
for (int i = 0; i < m; i++) {arr1[i] = arr[x + i];}
for (int j = 0; j < n; j++) {arr2[j] = arr[p + 1 + j];}
int i = 0;int j = 0;int k = x; //declaring variables i,j,k;
while (i<m && j<n) {
if (arr1[i] <= arr2[j])
arr[k] = arr1[i];
arr[k] = arr2[j];
// here we are copying remaining elements of arr1 if there are any
while (i < m) {
arr[k] = arr1[i];
// here we are copying remaining elements of arr2 if there are any
while (j < n) {
arr[k] = arr2[j];
void func1(int arr[],int x,int y){
int p =x+ (y-x)/2; //middle element
func1(arr,x,p); //merge sort for first half
func1(arr,p+1,y); //merge sort for second half
func(arr,x,p,y); //merging both halves
int main()
int n; //taking size of array as input from user
int arr[n];
for(int i=0;i<n;i++) { cin>>arr[i];} //taking values of array as input from user
cout << “Given array is: “;
for(int i=0;i<n;i++)
cout<<arr[i]<<” “; //printing the original array
func1(arr, 0, n — 1); //calling function func1
cout << “\nSorted array is: “;
for(int i=0;i<n;i++)
cout<<arr[i]<<” “; //printing the sorted array
return 0;


Code(for linked list)


Source —

Advantages of merge sort

  1. Merge sort is usually preferred for sorting a linked list since nodes may not be adjacent in memory. Also we know that we can insert elements in the middle of linked list if reference to previous node is given with O(1) extra space. So merge sort can be implemented without extra space.
  2. Merge sort works more efficiently and faster on larger data sets.
  3. Merge sort is a stable sorting technique.

Disadvantages of merge sort

  1. It is slower for smaller data sets as compared to other sorting techniques.
  2. Its space complexity is O(n) which means it requires a lot of space for creating a auxiliary array which it uses for storing.
  3. Even if the array is sorted, it will go through the whole process.

Time complexity

Recurrence relation

Space complexity

Differences between merge sort and quick sort

  1. Time complexity — Worst case complexity of quick sort is O(n²) whereas of merge sort is O(nlogn).
  2. Dataset — Quick sort is generally preferred for smaller arrays and is not preferred for larger datasets whereas merge sort works fine on any size of data.
  3. Storage space — Quick sort does not require any extra space whereas merge sort requires extra memory for auxiliary arrays.
  4. Efficiency — Quick sort works more efficiently and faster for shorter dataset whereas merge sort works more efficiently and faster for bigger dataset.
  5. Preference — Quick sort if preferred for arrays whereas merge sort is preferred for linked list.
  6. Method of sorting — In quick sort the data is stored in main memory, therefore it is internal sorting method whereas in merge sort, the data which is to be sorted cannot be stored in memory and it requires temporary memory ,so it is external sorting method.
  7. Stability — Quick sort is not stable but it can be made stable by doing some changes in the code whereas merge sort is stable.
  8. Locality of preference — It is good in case of quick sort and poor in case of merge sort.




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