Merge Sort C++: Examples & Implementation

A divide-and-conquer approach solves big problems by splitting them into smaller parts. The method makes each small task simple before putting solutions back together.

The main steps of divide-and-conquer are

• Problems get divided into smaller portions. This continues until each portion becomes easy to solve.
• Each small part receives its solution, often via recursion. Tiny parts get fixed right away.
• Everything comes together once all parts have solutions to fix the original problem.

A merge sort algorithm splits information into two halves and puts them back in order. It works by:

1. Breaking lists into tiny sections

2. Organizing those sections

3. Joining them back properly

The process shows excellent results with big data sets because it maintains O(nlogn) time complexity. Many applications prefer merge sort for this reason.

Algorithm of Merge Sort

MERGE_SORT(arr, start, end)  

    if start < end  
        set mid = (start + end) / 2  
        MERGE_SORT(arr, start, mid)  
        MERGE_SORT(arr, mid + 1, end)  
        MERGE(arr, start, mid, end)  
    end of if  

END MERGE_SORT  

How does Merge Sort Work?

To understand the merge sort c++ program. Let’s take an example array such as:

Step 1: Divide the array into two halves

Merge sort starts by dividing the array into two halves:

Step 2: Divide each half further

Next, each of these halves is divided again into smaller parts. We divide the left half into two arrays of size 2:

Step 3: Merge the two halves

Finally, we merge the two sorted halves:

Time and Space Complexity Analysis

• Time Complexity: O(nlog⁡n) for best, average, and worst cases.
• Space Complexity: O(n) due to the additional space required for merging.

Merge Sort Implementation

Implementing merge sort c++ code typically involves defining a merge function combining two sorted arrays and a mergeSort function recursively sorts the array.

void merge(int arr[], int left, int mid, int right) {
    // Code to merge two halves
}

void mergeSort(int arr[], int left, int right) {
    // Code to divide and conquer
}

• Merge functions combine two sorted subarrays into one by comparing their elements sequentially.
• The mergeSort function recursively divides the array until each subarray contains one element and then calls the merge function to combine them.

Here is the example c++ merge sort program:

Writing the Code for Merge Algorithm

1. The main function that implements the recursive merge sort algorithm.

2. The Parameters are :

• arr[]: The main array.
• left: The starting index of the subarray to be sorted.
• right: The ending index of the subarray to be sorted.

3. If left < right, continue the sorting process; otherwise, return.

4. The array is divided at the middle index.

5. The subarray on the left (arr[left..mid]) and the subarray on the right (arr[mid+1..right]) are recursively sorted using MergeSort.

6. After sorting both subarrays, the Merge function merges them into a single sorted array.

Code

#include <iostream>
using namespace std;

// Function to merge two sorted subarrays
void Merge(int arr[], int left, int mid, int right) {
    // Calculate the sizes of the two subarrays
    int n1 = mid - left + 1; // Size of left subarray
    int n2 = right - mid;    // Size of right subarray

    // Create temporary arrays for left and right subarrays
    int* L = new int[n1]; // Left subarray
    int* R = new int[n2]; // Right subarray

    // Copy data to temporary arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge the temporary arrays back into arr[left..right]
    int i = 0; // Initial index of first subarray
    int j = 0; // Initial index of second subarray
    int k = left; // Initial index of merged array

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy remaining elements of L[] if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy remaining elements of R[] if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    // Free dynamically allocated memory
    delete[] L;
    delete[] R;
}

// Function to implement merge sort
void MergeSort(int arr[], int left, int right) {
    if (left < right) {
        // Find the middle point
        int mid = left + (right - left) / 2;

        // Recursively sort first and second halves
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);

        // Merge the sorted halves
        Merge(arr, left, mid, right);
    }
}

// Main function to execute the program
int main() {
    // Example array to be sorted
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate number of elements

    cout << "Original Array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    
    cout << endl;

    MergeSort(arr, 0, n - 1); // Call merge sort on the array

    cout << "Sorted Array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    cout << endl;

    return 0;
}

Explanation

• The merge function merges two sorted subarrays into a single sorted array. It uses temporary arrays to hold the values from the left and right halves.
• It calls MergeSort to sort the array.
• Finally, it prints the sorted array.

Output

Original Array: 38 27 43 3 9 82 10 
Sorted Array: 3 9 10 27 38 43 82 

Recurrence Relation of Merge Sort

The recurrence relation for Merge Sort is a mathematical expression that describes the algorithm's time complexity in terms of the input size. The relation can be derived based on the algorithm's divide-and-conquer approach.

The recurrence relation for Merge Sort can be expressed as:

Explanation of each element:

• T(n): Represents the total time complexity for sorting an array of size n.
• 2T(n/2): This term accounts for the two recursive calls made on subarrays of size n/2​. Each call sorts half of the array.‍
• O(n): This term represents the linear time required to merge the two sorted subarrays.

Merge Sort is an efficient sorting algorithm with an O(n log n) time complexity. It can be implemented in two ways: Recursive Merge Sort and Iterative Merge Sort. Let’s dive into these methods, explaining their respective processes and offering C++ code examples.

Recursive Merge Sort

Recursive Merge Sort follows a divide-and-conquer approach, where the array is recursively split into two halves, each half is sorted, and then the two halves are merged back into a sorted array. The recursion continues until each subarray contains a single element (which is trivially sorted), and then the merge process begins.

Recursive Merge Sort C++ Implementation:

#include <iostream>
using namespace std;

// Merge two sorted subarrays
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
    int i = 0, j = 0, k = 0;
    while (i < leftSize && j < rightSize) {
        arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    }
    while (i < leftSize) arr[k++] = left[i++];
    while (j < rightSize) arr[k++] = right[j++];
}

// Recursive Merge Sort function
void recursiveMergeSort(int arr[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    recursiveMergeSort(arr, left, mid);         // Sort left half
    recursiveMergeSort(arr, mid + 1, right);    // Sort right half

    int leftArr[mid - left + 1], rightArr[right - mid];
    for (int i = 0; i <= mid - left; i++) leftArr[i] = arr[left + i];
    for (int i = 0; i < right - mid; i++) rightArr[i] = arr[mid + 1 + i];
    merge(arr, leftArr, mid - left + 1, rightArr, right - mid);  // Merge
}

// Driver code to test
int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    recursiveMergeSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

Output

Original array: 38 27 43 3 9 82 10 
Sorted array: 9 9 10 82 3 82 10

Explanation

• The function recursiveMergeSort recursively divides the array into two halves.
• The base case occurs when the array cannot be divided further (i.e., the subarray size is 1).
• The merge function merges two sorted arrays back into a single sorted array.

Iterative Merge Sort

While Recursive Merge Sort divides and conquers the problem by calling itself recursively, Iterative Merge Sort does the same task without recursion. Instead, it progressively merges pairs of adjacent elements or subarrays in a bottom-up manner.

Iterative Merge Sort C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

// Merge two sorted subarrays
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left;
    while (i < leftArr.size() && j < rightArr.size()) {
        arr[k++] = (leftArr[i] <= rightArr[j]) ? leftArr[i++] : rightArr[j++];
    }
    while (i < leftArr.size()) arr[k++] = leftArr[i++];
    while (j < rightArr.size()) arr[k++] = rightArr[j++];
}

// Iterative Merge Sort
void iterativeMergeSort(vector<int>& arr) {
    int n = arr.size();
    for (int currSize = 1; currSize < n; currSize *= 2) {
        for (int left = 0; left < n; left += 2 * currSize) {
            int mid = min(left + currSize - 1, n - 1);
            int right = min(left + 2 * currSize - 1, n - 1);
            merge(arr, left, mid, right);
        }
    }
}

// Driver code
int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    cout << "Original array: ";
    for (int i : arr) cout << i << " ";
    cout << endl;

    iterativeMergeSort(arr);

    cout << "Sorted array: ";
    for (int i : arr) cout << i << " ";
    cout << endl;

    return 0;
}

Output

Original array: 38 27 43 3 9 82 10 
Sorted array: 3 9 10 27 38 43 82

Explanation

• The function iterativeMergeSort starts with a subarray size of 1 and doubles the size in each iteration.
• It uses a loop to merge adjacent pairs of subarrays at each step.
• The merge function combines the two sorted halves into one sorted array.

• Merge sort is particularly well-suited for linked lists because it does not require random access to elements. This makes it ideal when you need to merge two sorted arrays in C++, as the linked list structure allows easy splitting and merging without the need for random access.
• It is used in external sorting algorithms where data to be sorted does not fit into memory, as it efficiently handles large datasets by dividing them into smaller chunks.
• Merge sort maintains the relative order of equal elements, making it ideal for sorting data structures where stability is essential, such as sorting records in databases.
• The divide-and-conquer approach allows for easy parallelisation, making it suitable for multi-threaded applications.

• Merge sort has a consistent time complexity of O(nlogn) for best, average, and worst cases, making it efficient for large datasets.
• It is a stable sorting algorithm, preserving the relative order of equal elements.
• Compared to quicksort, which can degrade to O(n²) in the worst case, merge sort guarantees O(nlogn) performance regardless of input.
• Works Well with Linked Lists: It can be implemented without extra space when sorting linked lists, as merging can be done in place.

• Merge sort requires additional space proportional to the size of the input array (O(n)), which can be a drawback for large datasets.
• The recursive nature and merging process introduce overhead compared to simpler algorithms like insertion or selection sort for small datasets.
• The standard implementation is not an in-place algorithm since it requires extra storage for temporary arrays.

Here are the coding questions with c++ code asked in top companies' assessments on merge sort 

Problem Statement 1:

Given an array, count the number of inversions in the array. An inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j].

Sample Input:
5
2, 3, 8, 6, 1]
Output:
5

Code

#include <iostream>
using namespace std;

int mergeAndCount(int arr[], int left, int mid, int right) {
    int i = left; // Starting index for left subarray
    int j = mid + 1; // Starting index for right subarray
    int k = left; // Starting index to be sorted
    int inv_count = 0;

    // Create a temporary array
    int temp[right + 1];
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inv_count += (mid - i + 1); // Count inversions
        }
    }

    // Copy remaining elements of left subarray
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    
    // Copy remaining elements of right subarray
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    
    // Copy sorted subarray into Original array
    for (int i = left; i <= right; i++) {
        arr[i] = temp[i];
    }

    return inv_count;
}

int mergeSortAndCount(int arr[], int left, int right) {
    int inv_count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;

        inv_count += mergeSortAndCount(arr, left, mid);
        inv_count += mergeSortAndCount(arr, mid + 1, right);
        inv_count += mergeAndCount(arr, left, mid, right);
    }
    return inv_count;
}

int main() {
    int n;
    
    cout << "Enter the number of elements in the array: ";
    cin >> n;

    int* arr = new int[n]; // Dynamically allocate array

    cout << "Enter the elements of the array:\n";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << "Number of inversions: " << mergeSortAndCount(arr, 0, n - 1) << endl;

    delete[] arr; // Free dynamically allocated memory
    return 0;
}

Output

Enter the number of elements in the array: 5
Enter the elements of the array:
2 3 8 6 1
Number of inversions: 5

Explanation

• In the above program a pair (i, j) where i < j and arr[i] > arr[j].
• It uses modified merge sort to count inversions during merging.
• Inversions are counted when elements from the right subarray are smaller than those in the left.
• Time complexity is O(nlogn).

Problem Statement 2:

Given k sorted arrays of different sizes, merge them into a single sorted array.

Sample Input:
arr1 = [1, 4, 7]
arr2 = [2, 5]
arr3 = [3, 6]

Output:

[1, 2, 3, 4, 5, 6, 7]

Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Element {
    int value;
    int arrayIndex;
    int elementIndex;

    bool operator>(const Element& other) const {
        return value > other.value; // Min-heap based on value
    }
};

vector<int> mergeKSortedArrays(vector<vector<int>>& arrays) {
    priority_queue<Element, vector<Element>, greater<Element>> minHeap;
    
    // Initialize the heap with the first element of each array
    for (int i = 0; i < arrays.size(); i++) {
        if (!arrays[i].empty()) {
            minHeap.push({arrays[i][0], i, 0});
        }
    }

    vector<int> mergedArray;

    while (!minHeap.empty()) {
        Element current = minHeap.top();
        minHeap.pop();
        
        mergedArray.push_back(current.value);

        // If there is a next element in the same array
        if (current.elementIndex + 1 < arrays[current.arrayIndex].size()) {
            minHeap.push({arrays[current.arrayIndex][current.elementIndex + 1], current.arrayIndex,
                           current.elementIndex + 1});
        }
    }

    return mergedArray;
}

int main() {
    int k;
    
    cout << "Enter number of sorted arrays: ";
    cin >> k;

    vector<vector<int>> arrays(k);
    
    for (int i = 0; i < k; i++) {
        int n;
        cout << "Enter number of elements in array " << (i + 1) << ": ";
        cin >> n;
        
        cout << "Enter elements of array " << (i + 1) << ": ";
        arrays[i].resize(n);
        
        for (int j = 0; j < n; j++) {
            cin >> arrays[i][j];
        }
    }

    vector<int> result = mergeKSortedArrays(arrays);
    
    cout << "Merged Array: ";
    for (int num : result) {
        cout << num << " ";
    }
    
    cout << endl;

    return 0;
}

Output

Enter number of sorted arrays: 3
Enter number of elements in array 1: 3
Enter elements of array 1: 1 4 7
Enter number of elements in array 2: 2
Enter elements of array 2: 2 5
Enter number of elements in array 3: 2
Enter elements of array 3: 3 6
Merged Array: 1 2 3 4 5 6 7 

Explanation

• The above program merges k sorted arrays into one sorted array.
• Utilises a min-heap to access the smallest element across arrays efficiently.
• Extracts the smallest element, add it to the result, and pushes the next element from the originating array.
• Time complexity is O(Nlogk), where N is the total elements and k is the number of arrays.

Problem Statement 3:

Given two sorted arrays A[] and B[] of sizes N and M, the task is to merge both arrays into a single array in non-decreasing order.

Sample Input
3
1  3   5
3
2   4  6

Output
1 2 3 4 5 6 

Code

#include <iostream>
using namespace std;

void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[]) {
    int i = 0, j = 0, k = 0;

    // Merge both arrays
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            arr3[k++] = arr1[i++];
        } else {
            arr3[k++] = arr2[j++];
        }
    }

    // Copy remaining elements from arr1[]
    while (i < n1) {
        arr3[k++] = arr1[i++];
    }

    // Copy remaining elements from arr2[]
    while (j < n2) {
        arr3[k++] = arr2[j++];
    }
}

int main() {
    int n1, n2;
    
    // Input for the first sorted array
    cout << "Enter the number of elements in the first sorted array: ";
    cin >> n1;
    
    int* arr1 = new int[n1]; // Dynamically allocate memory for the first array
    cout << "Enter elements of the first sorted array:\n";
    for (int i = 0; i < n1; i++) {
        cin >> arr1[i];
    }

    // Input for the second sorted array
    cout << "Enter the number of elements in the second sorted array: ";
    cin >> n2;
    
    int* arr2 = new int[n2]; // Dynamically allocate memory for the second array
    cout << "Enter elements of the second sorted array:\n";
    for (int i = 0; i < n2; i++) {
        cin >> arr2[i];
    }

    // Merged array
    int* mergedArray = new int[n1 + n2];
    
    // Merge the two arrays
    mergeArrays(arr1, arr2, n1, n2, mergedArray);
    
    // Output the merged array
    cout << "Merged Array: ";
    for (int i = 0; i < n1 + n2; i++) {
        cout << mergedArray[i] << " ";
    }
    
    cout << endl;

    // Free dynamically allocated memory
    delete[] arr1;
    delete[] arr2;
    delete[] mergedArray;

    return 0;
}

Output

Enter the number of elements in the first sorted array: 3
Enter elements of the first sorted array:
1 3 5
Enter the number of elements in the second sorted array: 3
Enter elements of the second sorted array:
2 4 6
Merged Array: 1 2 3 4 5 6 

Explanation

• In the above program, the arrays compare elements and add the smaller one to a merged array.
• Adds leftover elements from the other array.
• Prints the merged array and frees allocated memory.

In conclusion, merge sort c++ is an efficient and stable sorting algorithm that uses the divide-and-conquer strategy, achieving a time complexity of O(nlogn). It is mainly used in handling large datasets and maintains the relative order of equal elements, making it ideal for applications requiring stability. While it is particularly effective for sorting linked lists and external data, its requirement for additional memory can be a drawback in memory-constrained environments. Merge Sort's predictable performance and versatility make it a valuable tool in C++ programming, suitable for various applications where efficient sorting is essential.

1. What is the time complexity of Merge Sort in C++?

The time complexity of Merge Sort Program in C++:

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n log n)

2. How does Merge Sort Compare to QuickSort?

• Both have an average time complexity of O(n log n), but QuickSort performs faster in practice due to better locality of reference and fewer memory accesses.
• Merge Sort requires O(n) extra space, while QuickSort can be implemented with O(log n) space (in the best case).
• Merge Sort is stable, while QuickSort is not.

3. Can Merge Sort be used for linked lists?

Yes, Merge Sort is very efficient for linked lists because linked lists allow easy splitting and merging operations. When sorting linked lists, you don't need extra space for arrays as in the case of arrays, and Merge Sort can be implemented in O(n log n) time with O(1) extra space.

1. What is the time complexity of Merge Sort in the worst case?

a) O(n)

b) O(n log n)

c) O(log n)

d) O(n^2)

Answer: b) O(n log n)

2. Which type of algorithm is the merge sort?

a) Divide and Conquer

b) Greedy Algorithm

c) Dynamic Programming

d) Backtracking

Answer: a) Divide and Conquer

3. What is the space complexity of Merge Sort?

a) O(1)

b) O(n)

c) O(log n)

d) O(n^2)

Answer: b) O(n)

4. What is the best case time complexity for Merge Sort?

a) O(n)

b) O(n log n)

c) O(log n)

d) O(n^2)

Answer: b) O(n log n)