Merge Sort

When your life gets overwhelming, remember that you can handle anything if you break it down. Divide your challenges, conquer them individually, and merge the outcomes into a stronger, more organized you.

Like always, try out the problem first for best results.

Problem: Sort an Array (LeetCode Link): Given an array of integers nums, sort the array in ascending order. 💡 HintCan you break the problem down into smaller, easier-to-solve subproblems?

There are many sorting algorithms to choose from, but for this chapter, we will focus on Divide and Conquer sorting algorithms, specifically Merge Sort.

How It Works

Merge Sort follows a simple, recursive three-step process:

1. Divide: The array is recursively split in half until each subarray contains only one element. A single-element array is inherently sorted.
2. Conquer: This step is implicit. Since the base case is a single-element array, which is already sorted, there's nothing to "conquer" in the traditional sense.
3. Combine (Merge): This is the core of the algorithm. Two sorted subarrays are merged to produce a new, larger sorted subarray. This process is repeated up the recursion stack until all subarrays are merged back into a single, fully sorted array.

Walkthrough: Implementing Merge Sort

def merge(left, right):
    sorted_array = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1
    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])
    return sorted_array

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    return merge(left_half, right_half)

# Example usage:
# sorted_nums = merge_sort(nums)

private void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[] = new int[n1];
    int R[] = new int[n2];

    for (int i = 0; i < n1; ++i)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[m + 1 + j];

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

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

public void sort(int[] arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        sort(arr, l, m);
        sort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

// Example usage:
// sort(nums, 0, nums.length - 1);

void merge(vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0;
    int j = 0;
    int k = l;

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

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) {
        return;
    }
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

// Example usage:
// mergeSort(nums, 0, nums.size() - 1);

Complexity Analysis

• Time Complexity: $O(N log N)$ - The array is split in half log N times, and each merge operation takes $O(N)$ time.
• Space Complexity: $O(N)$ - Additional space is required to store the merged subarrays.

Variation: Quick Sort

Quick Sort is another efficient, in-place sorting algorithm that also uses a divide and conquer strategy.

• How it Works: It picks an element as a pivot and partitions the given array around the picked pivot.
• Practice Problem: Kth Largest Element in an Array (LeetCode Link). 💡 HintUse the partitioning logic of Quick Sort to find the kth largest element.

More Problems & Variations

1. Merge k Sorted Lists: Merge k sorted linked lists into one sorted linked list. 💡 HintYou can use the merge logic from Merge Sort to combine the lists iteratively.
2. Count of Smaller Numbers After Self: You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]. 💡 HintModify the merge step of Merge Sort to count the smaller elements.