LeetCode:

• https://leetcode.com/problems/sort-an-array/description/?envType=problem-list-v2&envId=merge-sort

Principles of Merge Sort

Merge sort is a comparison-based sorting algorithm that follows the divide and conquer strategy. It works recursively dividing the array into smaller subarrays, sorting each subarray individually, and then merging them back together in sorted order.

Algorithm

1. Divide: Split the unsorted array into two equal halves recursively until each subarray contains only one element.
2. Conquer: Sort each subarray individually using Merge Sort.
3. Merge: Merge the sorted subarrays back together to form the single sorted array. This merging process involves comparing elements from the two subarrays and selecting the smaller element to place in the final sorted array.

Dry Run:

[38, 27, 43, 3, 9, 82, 10]

Step 1: Divide the Array Recursively:

                      [38, 27, 43, 3, 9, 82, 10]

Split 1:         [38, 27, 43, 3]            [9, 82, 10]
Split 2:      [38, 27]       [43, 3]     [9, 82]     [10]
Split 3:    [38]   [27]     [43]   [3]  [9]   [82]   [10]

Now, each subarray has only one element. Now begin the conquer and merge phase.

Step 2: Merge Subarrays:

Starting from the smallest subarrays, merge each pair back together in sorted order.

Merge Step-by-Step

1. Merge [38] and [27] → [27, 38]
2. Merge [43] and [3] → [3, 43]
3. Merge [9] and [82] → [9, 82]

[27, 38]   [3, 43]   [9, 82]   [10]

• Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
• Merge [9, 82] and [10] → [9, 10, 82]

[3, 27, 38, 43]   [9, 10, 82]

6. Merge [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Final Sorted Array:

After all the merges, the final sorted array is:

[3, 9, 10, 27, 38, 43, 82]

Code

#include <bits/stdc++.h>
using namespace std;

void merge(vector<int> &arr, int low, int mid, int high) {
    vector<int> temp; // temporary array
    int left = low;      // starting index of left half of arr
    int right = mid + 1;   // starting index of right half of arr

    //storing elements in the temporary array in a sorted manner//

    while (left <= mid && right <= high) {
        if (arr[left] <= arr[right]) {
            temp.push_back(arr[left]);
            left++;
        }
        else {
            temp.push_back(arr[right]);
            right++;
        }
    }

    // if elements on the left half are still left

    while (left <= mid) {
        temp.push_back(arr[left]);
        left++;
    }

    //  if elements on the right half are still left
    while (right <= high) {
        temp.push_back(arr[right]);
        right++;
    }

    // transfering all elements from temporary to arr
    for (int i = low; i <= high; i++) {
        arr[i] = temp[i - low];
    }
}

void mergeSort(vector<int> &arr, int low, int high) {
    if (low >= high) return;
    int mid = (low + high) / 2 ;
    mergeSort(arr, low, mid);  // left half
    mergeSort(arr, mid + 1, high); // right half
    merge(arr, low, mid, high);  // merging sorted halves
}

int main() {

    vector<int> arr = {9, 4, 7, 6, 3, 1, 5}  ;
    int n = 7;

    cout << "Before Sorting Array: " << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "  ;
    }
    cout << endl;
    mergeSort(arr, 0, n - 1);
    cout << "After Sorting Array: " << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "  ;
    }
    cout << endl;
    return 0 ;
}

Complexity Analysis

• Time Complexity: O(n log n)
  • At each step, we divide the whole array, for that logn and we assume n steps are taken to get sorted array, so overall time complexity will be nlogn.
• Space Complexity: O(n)
  • We are using a temporary array to store elements in sorted order.