Merge Sort in C++

What is Merge Sort in C++?

Merge sort is one the sorting technique that is used to sort the data in a logical order. It uses divide and conquer approach for sorting the data. Merge sort repeatedly breaks down a list into several sub lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list. In this article, we will read more about merge sort in C++.

merging
Time Complexity Θ(n Log n)
Best Case Ω(n Log n)
Worst Case O(n Log n)
Space Complexity O(n)

Merge Sort in C++

  • A file of any size can be sorted using merge sort.
  • Elements in the merge sort are divided into two sub list again and again until each sub-list contain only one element.
  • After this, the elements are merged to make a sorted list.
  • It requires more space and is less efficient
Merge Sort in C++

Execution of Merge sort in C++

Merge sort is executed in three steps:-

1.) Divide Step:

First of all the array will be divide in to  N sub list, until each sub list contains only one element.

2.) Conquer Step:

Take two sub list and place them in logical order.

3.) Combine Step:

Combine the elements back by merging the two sorted sub list into a sorted sequence.

Merge Sort in Cpp

Program for merge sort in C++

We will look at two different methods, both have the same time complexity with the difference that –

  • Method 1 – Uses two temp subarrays
  • Method 2 – Uses 1 temp subarray

The combined size of two temp subarrays in method 1 is the same as the whole array in method 2. So the space complexity remains the same.

#include<iostream>
using namespace std;

void mergeSort(int[],int,int); 
void merge(int[],int,int,int);

void printArray(int arr[], int size){
    int i;
    for(i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() 
{
    int array[]= {8, 4, 5, 1, 3, 9, 0, 2, 7, 6};
    int i; 

    int size = sizeof(array)/sizeof(array[0]);
    printArray(array, size);

    mergeSort(array, 0, size-1); 
    printArray(array, size);
}

void mergeSort(int a[], int left, int right)
{
    int mid;
    if(left < right)
    {
        // can also use mid = left + (right - left) / 2
        // this can avoid data type overflow
        mid = (left + right)/2;
        
        // recursive calls to sort first half and second half subarrays
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // create temp arrays to store left and right subarrays
    int L[n1], R[n2];
    
    // Copying data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
        
    // here we merge the temp arrays back into arr[l..r]
    i = 0; // Starting index of L[i]
    j = 0; // Starting index of R[i]
    k = left; // Starting index of merged subarray
    
    while (i < n1 && j < n2) 
    {
        // place the smaller item at arr[k] pos
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // Copy the remaining elements of L[], if any 
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // Copy the remaining elements of R[], if any 
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Output

8 4 5 1 3 9 0 2 7 6 
0 1 2 3 4 5 6 7 8 9
#include<iostream>
using namespace std;

void mergeSort(int[],int,int); 
void merge(int[],int,int,int);

void printArray(int arr[], int size){
    int i;
    for(i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() 
{
    int array[]= {8, 4, 5, 1, 3, 9, 0, 2, 7, 6};
    int i; 

    int size = sizeof(array)/sizeof(array[0]);
    printArray(array, size);

    mergeSort(array, 0, size-1); 
    printArray(array, size);
}

void mergeSort(int a[], int left, int right)
{
    int mid;
    if(left < right)
    {
        // can also use mid = left + (right - left) / 2
        // this can avoid data type overflow
        mid = (left + right)/2;
        
        // recursive calls to sort first half and second half subarrays
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

void merge(int a[], int left, int mid, int right)
{
    int i = left; // starting index of left subarray
    int j = mid + 1; // starting index of right subarray
    int index = left; // used to place items in temp[]
    int temp[10];

    while(i<=mid && j<=right)
    {
        // place the smaller item at temp[index]
        if(a[i] < a[j]) 
{
temp[index] = a[i];
i = i+1;
}
else
{
temp[index] = a[j];
j = j+1;
}
index++;
}

// i > mid would mean all items for left // subarray were successfully placed, and there // must be unplaced right subarray items if(i>mid) { while(j<=right) { temp[index] = a[j]; index++; j++; } } // else all items of right subarray must have // been placed and there must be // unplaced items in the left-subarray else { while(i<=mid) { temp[index] = a[i]; index++; i++; } } int p = left; // left index of subarray // by now index would have reached right // most index of right subarray // placing all items of temp[] into actual array a[] while(p < index) { a[p]=temp[p]; p++; } }

Output

8 4 5 1 3 9 0 2 7 6 
0 1 2 3 4 5 6 7 8 9

Performance

Strengths

  • With a good time complexity of O(n log n), merge sort is great !!!
  • Good to learn Divide and conquer algorithm later used in Dynamic Programming concepts

Weakness

  • Poor space complexity of O(n)
  • Lots of overhead in copying data between arrays and making new arrays
Merge sort in C++ meme
Quiz time

Fun Fact

Merge Sort is useful for sorting linked lists. Merge Sort is a stable sort which means that the same element in an array maintain their original positions with respect to each other. Overall time complexity of Merge sort is O(nLogn).

2 comments on “Merge Sort in C++”