Merge Sort

Definition

A divide-and-conquer sorting algorithm that recursively divides the array into halves, sorts them, and merges the sorted halves back together.

Key Steps: 1. DIVIDE: Split array into two halves 2. CONQUER: Recursively sort each half 3. COMBINE: Merge sorted halves

---

Big O Complexity

---

When to Use

---

Pros and Cons

---

Implementation

Standard Merge Sort

public void mergeSort(int[] arr) {
    if (arr.length < 2) return;
    mergeSort(arr, 0, arr.length - 1);
}

private void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;

    // Divide
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // Conquer
    merge(arr, left, mid, right);
}

private void merge(int[] arr, int left, int mid, int right) {
    // Create temp arrays
    int[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
    int[] rightArr = Arrays.copyOfRange(arr, mid + 1, right + 1);

    int i = 0, j = 0, k = left;

    // Merge back
    while (i < leftArr.length && j < rightArr.length) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    // Copy remaining
    while (i < leftArr.length) arr[k++] = leftArr[i++];
    while (j < rightArr.length) arr[k++] = rightArr[j++];
}

Optimized with Reusable Buffer

public void mergeSortOptimized(int[] arr) {
    int[] temp = new int[arr.length];
    mergeSort(arr, temp, 0, arr.length - 1);
}

private void mergeSort(int[] arr, int[] temp, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, temp, left, mid);
    mergeSort(arr, temp, mid + 1, right);

    // Skip merge if already sorted
    if (arr[mid] <= arr[mid + 1]) return;

    merge(arr, temp, left, mid, right);
}

private void merge(int[] arr, int[] temp, int left, int mid, int right) {
    // Copy to temp
    System.arraycopy(arr, left, temp, left, right - left + 1);

    int i = left, j = mid + 1, k = left;

    while (i <= mid && j <= right) {
        if (temp[i] <= temp[j]) {
            arr[k++] = temp[i++];
        } else {
            arr[k++] = temp[j++];
        }
    }

    // Only need to copy left remainder (right already in place)
    while (i <= mid) arr[k++] = temp[i++];
}

Bottom-Up (Iterative) Merge Sort

public void mergeSortBottomUp(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];

    // Size of subarrays to merge: 1, 2, 4, 8, ...
    for (int size = 1; size < n; size *= 2) {
        // Merge subarrays of current size
        for (int left = 0; left < n - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = Math.min(left + 2 * size - 1, n - 1);
            merge(arr, temp, left, mid, right);
        }
    }
}

Merge Sort for Linked List

// O(1) space for linked lists (no array copy needed)
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;

    // Find middle
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Split
    ListNode mid = slow.next;
    slow.next = null;

    // Recursively sort
    ListNode left = sortList(head);
    ListNode right = sortList(mid);

    // Merge
    return mergeLists(left, right);
}

private ListNode mergeLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

---

Applications

Count Inversions

// Inversion: pair (i,j) where i < j but arr[i] > arr[j]
public int countInversions(int[] arr) {
    int[] temp = new int[arr.length];
    return mergeSort(arr, temp, 0, arr.length - 1);
}

private int mergeSort(int[] arr, int[] temp, int left, int right) {
    int count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        count += mergeSort(arr, temp, left, mid);
        count += mergeSort(arr, temp, mid + 1, right);
        count += merge(arr, temp, left, mid, right);
    }
    return count;
}

private int merge(int[] arr, int[] temp, int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    int inversions = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inversions += (mid - i + 1);  // All remaining in left are inversions
        }
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    System.arraycopy(temp, left, arr, left, right - left + 1);
    return inversions;
}

Merge K Sorted Arrays

public int[] mergeKArrays(int[][] arrays) {
    return mergeKArrays(arrays, 0, arrays.length - 1);
}

private int[] mergeKArrays(int[][] arrays, int start, int end) {
    if (start == end) return arrays[start];

    int mid = start + (end - start) / 2;
    int[] left = mergeKArrays(arrays, start, mid);
    int[] right = mergeKArrays(arrays, mid + 1, end);

    return mergeTwoArrays(left, right);
}

private int[] mergeTwoArrays(int[] a, int[] b) {
    int[] result = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) result[k++] = a[i++];
        else result[k++] = b[j++];
    }
    while (i < a.length) result[k++] = a[i++];
    while (j < b.length) result[k++] = b[j++];

    return result;
}

External Merge Sort

// Pseudocode for sorting data larger than memory
/*
1. Divide file into chunks that fit in memory
2. Sort each chunk using in-memory sort
3. Write sorted chunks to temporary files
4. Merge sorted files using k-way merge
   - Use min-heap for efficient k-way merge
   - Read one buffer at a time from each file
*/

public void externalSort(String inputFile, String outputFile, int memoryLimit) {
    // Phase 1: Create sorted runs
    List<String> sortedRuns = new ArrayList<>();
    // Read chunks, sort in memory, write to temp files

    // Phase 2: Merge sorted runs
    // Use priority queue for k-way merge
    PriorityQueue<BufferedReader> pq = new PriorityQueue<>(
        (a, b) -> compareNextLines(a, b)
    );
    // Read from all files, write minimum to output
}

---

Parallel Merge Sort

import java.util.concurrent.*;

public class ParallelMergeSort {
    private static final int THRESHOLD = 1000;

    public static void parallelSort(int[] arr) throws Exception {
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new MergeSortTask(arr, 0, arr.length - 1, new int[arr.length]));
    }

    static class MergeSortTask extends RecursiveAction {
        int[] arr, temp;
        int left, right;

        MergeSortTask(int[] arr, int left, int right, int[] temp) {
            this.arr = arr;
            this.left = left;
            this.right = right;
            this.temp = temp;
        }

        @Override
        protected void compute() {
            if (right - left < THRESHOLD) {
                // Use sequential sort for small arrays
                Arrays.sort(arr, left, right + 1);
                return;
            }

            int mid = left + (right - left) / 2;

            // Fork both halves
            MergeSortTask leftTask = new MergeSortTask(arr, left, mid, temp);
            MergeSortTask rightTask = new MergeSortTask(arr, mid + 1, right, temp);

            invokeAll(leftTask, rightTask);

            merge(arr, temp, left, mid, right);
        }
    }
}

---

Tips & Tricks

---