Obsidian Notes

Merge Sort

3 min read

Merge Sort

1. Intuition & Framework

  • Pattern: Divide and Conquer.
  • Core Idea: Recursively split the array in half until sub-arrays contain a single element (which is inherently sorted), then zip the sorted halves back together.
  • Key Mechanisms:
  • Divide: mid = low + (high - low) / 2 splits the range [low, high] into [low, mid] and [mid + 1, high].
  • Conquer: A two-pointer merge zip (left starting at low, right starting at mid + 1).

2. Complexity Analysis

  • Time Complexity: across all cases (Best, Average, Worst). Splitting takes levels, and merging takes total work per level.
  • Space Complexity: auxiliary space for the temporary array (temp) used during the merge step.

3. Implementation

class Solution {
    // Main driver function for the Merge Sort algorithm
    public void mergeSort(int[] arr, int low, int high) {
        // Base case: If the range has 0 or 1 element, it is already sorted
        if (low >= high) {
            return;
        }
 
        // Calculate the middle index safely to avoid integer overflow
        int mid = low + (high - low) / 2;
 
        // 1. DIVIDE: Recursively sort the left half
        mergeSort(arr, low, mid);
 
        // 2. DIVIDE: Recursively sort the right half
        mergeSort(arr, mid + 1, high);
 
        // 3. COMBINE: Merge the two sorted halves back together
        merge(arr, low, mid, high);
    }
 
    // Helper function to merge two sorted sections of the array
    private void merge(int[] arr, int low, int mid, int high) {
        // Create a temporary array to store the merged result
        int[] temp = new int[high - low + 1];
        
        // Initialize pointers for tracking elements
        int left = low;      // Points to the start of the left half
        int right = mid + 1; // Points to the start of the right half
        int k = 0;           // Points to the index in the temporary array
 
        // Compare elements from both halves and pick the smaller one
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp[k++] = arr[left++];
            } else {
                temp[k++] = arr[right++];
            }
        }
 
        // Copy any leftover elements from the left half
        while (left <= mid) {
            temp[k++] = arr[left++];
        }
 
        // Copy any leftover elements from the right half
        while (right <= high) {
            temp[k++] = arr[right++];
        }
 
        // Copy the sorted elements from the temporary array back into the original array
        for (int i = low; i <= high; i++) {
            arr[i] = temp[i - low];
        }
    }
}

4. Important Notes

  • Index Mapping: temp[i - low] aligns the range [low, high] of arr with 0-based indexing of temp.
  • Stability: Using <= in arr[left] <= arr[right] ensures that equal elements retain their relative original order, keeping the sort stable.

Backlinks