Merge Sort

Design and Analysis of algorithm

What is merge sort?

Merge sort is one of the most efficient sorting technique which was founded by John von Neumann in 1945. It is based on Divide and Conquer algorithm .It breaks down a problem into two or more sub-problems of the same type, till these become simple enough to get solved.

Divide and conquer algorithm

In this approach, the problem is divided into sub-problems which are solved independently. After that the solution of sub-problems are finally merged up so that we can get the solution. It is divided in a 3 step process namely divide/break, conquer/solve and merge/combine.

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 - (https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/)

An example demonstrating merge sort for a singly linked list. Source — (https://iq.opengenus.org/merge-sort-a-singly-linked-list/)

Pseudocode

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];
 i++;
 }
 else 
 {
 arr[k] = arr2[j];
 j++;
 }
 k++;
 }
 // here we are copying remaining elements of arr1 if there are any
 while (i < m) {
 arr[k] = arr1[i];
 i++;
 k++;
 }
 // here we are copying remaining elements of arr2 if there are any
 while (j < n) {
 arr[k] = arr2[j];
 j++;
 k++;
 }}
void func1(int arr[],int x,int y){
 if(x<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
 cin>>n;
 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;
}

Output

The above code will firstly take the size and values of the array from the user. Then it will print the original array followed by the sorted array.

Code(for linked list)

Source — https://www.tutorialspoint.com/cplusplus-program-to-implement-merge-sort-algorithm-on-linked-list

Output

Source — https://www.tutorialspoint.com/cplusplus-program-to-implement-merge-sort-algorithm-on-linked-list

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

Best, average and worst case time complexity of merge sort is O(nlogn). Since we have read in Binary search that when a number is divided into half at every step , we can represent it using logarithmic function (log n) and (log n+1) represents the number of steps(at most). To find the middle of a subarray we perform a operation which is just a single step operation which would be O(1). Since here we divide the array (of n elements) into sub-arrays , to again merge the sub-arrays , a running time of O(n) would be required. Summing all these the time complexity of all the three cases of merge sort becomes n(l+logn) which is equal to O(nlogn).

Recurrence relation

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

Space complexity

Space complexity of merge sort is O(n).

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.

Overview

So today we saw how merge sort works along with its advantages , disadvantages, time complexity, space complexity , pseudocode, code and its comparison with quick sort. Hope you like the blog. Thank you!!