Merge Sort

Design and Analysis of algorithm

What is merge sort?

Divide and conquer algorithm

How merge sort works ?

For arrays

  1. Then list is sorted into halves till it cannot be further divided.
  2. These smaller lists are merged into new lists in sorted way.

For linked lists

  1. If step 1 does not follow then divide the linked list into 2 halves.
  2. After that the 2 halves are sorted.
  3. 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. Assign left as zero and right as n-1(where n is the number of variables).
  2. Calculate mid by (left + right)/2.
  3. Call function on (left,mid) and (mid+1,rear) and continue till left<right, else return.
  4. 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

Code(for 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 works more efficiently and faster on larger data sets.
  2. Merge sort is a stable sorting technique.

Disadvantages of merge sort

  1. Its space complexity is O(n) which means it requires a lot of space for creating a auxiliary array which it uses for storing.
  2. 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. 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.
  2. Storage space — Quick sort does not require any extra space whereas merge sort requires extra memory for auxiliary arrays.
  3. Efficiency — Quick sort works more efficiently and faster for shorter dataset whereas merge sort works more efficiently and faster for bigger dataset.
  4. Preference — Quick sort if preferred for arrays whereas merge sort is preferred for linked list.
  5. 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.
  6. Stability — Quick sort is not stable but it can be made stable by doing some changes in the code whereas merge sort is stable.
  7. Locality of preference — It is good in case of quick sort and poor in case of merge sort.

Overview

CSE student