Module 4.2 ⏱ 40 min read ⚡ Sorting & Divide-and-Conquer

Divide and Conquer (Merge Sort & Quick Sort)

Master recursive divide-and-conquer paradigms, stable merging mechanics, optimal pivot selection, and advanced inversion counting.

1. The Divide-and-Conquer Paradigm & Merge Sort

The divide-and-conquer strategy breaks a complex problem into smaller subproblems of the same type, solves them recursively, and then combines their results to construct the final solution. Merge Sort is a classic manifestation of this technique: it splits an array down the middle, recursively sorts both halves, and merges them back together in linear time.

Because merging always processes elements sequentially, Merge Sort maintains structural stability and guarantees an optimal $O(n \log n)$ time complexity across worst, average, and best-case scenarios, at the cost of $O(n)$ extra auxiliary memory space.

2. Quick Sort & Partitioning Strategies

Unlike Merge Sort, Quick Sort is an in-place sorting algorithm that partitions an array around a chosen pivot element. Elements smaller than the pivot are moved to its left, and larger elements are moved to its right. The subarrays are then sorted recursively.

Worst-Case Handling: While Quick Sort runs in $O(n \log n)$ on average, poorly chosen pivots (such as always picking the first or last element on already sorted data) can degrade performance to $O(n^2)$. This is mitigated in production environments using randomized pivot selection or the median-of-three technique.

// C++ Solution: Merge Sort Implementation
#include <vector>

class Solution {
public:
    std::vector<int> sortArray(std::vector<int>& nums) {
        if (nums.size() <= 1) return nums;
        int mid = nums.size() / 2;
        std::vector<int> left(nums.begin(), nums.begin() + mid);
        std::vector<int> right(nums.begin() + mid, nums.end());
        left = sortArray(left);
        right = sortArray(right);
        return merge(left, right);
    }
private:
    std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
        std::vector<int> res;
        int i = 0, j = 0;
        while (i < left.size() && j < right.size()) {
            if (left[i] <= right[j]) res.push_back(left[i++]);
            else res.push_back(right[j++]);
        }
        while (i < left.size()) res.push_back(left[i++]);
        while (j < right.size()) res.push_back(right[j++]);
        return res;
    }
};
            

# Python Solution: Merge Sort Implementation
class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])
        return self.merge(left, right)

    def merge(self, left: list[int], right: list[int]) -> list[int]:
        res = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                res.append(left[i])
                i += 1
            else:
                res.append(right[j])
                j += 1
        res.extend(left[i:])
        res.extend(right[j:])
        return res
            

// Java Solution: Merge Sort Implementation
import java.util.Arrays;

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums.length <= 1) return nums;
        int mid = nums.length / 2;
        int[] left = sortArray(Arrays.copyOfRange(nums, 0, mid));
        int[] right = sortArray(Arrays.copyOfRange(nums, mid, nums.length));
        return merge(left, right);
    }

    private int[] merge(int[] left, int[] right) {
        int[] res = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) res[k++] = left[i++];
            else res[k++] = right[j++];
        }
        while (i < left.length) res[k++] = left[i++];
        while (j < right.length) res[k++] = right[j++];
        return res;
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for both Merge Sort and Quick Sort, and tackle the Count Inversions problem using modified merge mechanics.

Quick Check: Test Your Intuition

What is the key structural and space difference between Merge Sort and Quick Sort?