Merge Sort

Merge sort is a divide-and-conquer algorithm that divides the array into halves, recursively sorts them, then merges the sorted halves.

Algorithm Steps

1. Divide: Split array into two halves
2. Conquer: Recursively sort each half
3. Combine: Merge the two sorted halves

Visual Example

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

Divide Phase:
[38, 27, 43, 3] → [38, 27] [43, 3] → [38] [27] [43] [3]
[9, 82, 10] → [9, 82] [10] → [9] [82] [10]

Merge Phase:
[27, 38] [3, 43] → [3, 27, 38, 43]
[9, 82] [10] → [9, 10, 82]

Final Merge:
[3, 27, 38, 43] [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Java Implementation

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Merge sorted halves
        merge(arr, left, mid, right);
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    // Create temporary 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 elements in sorted order
    while (i < leftArr.length && j < rightArr.length) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }
    
    // Copy remaining elements
    while (i < leftArr.length) {
        arr[k++] = leftArr[i++];
    }
    while (j < rightArr.length) {
        arr[k++] = rightArr[j++];
    }
}

In-Place Merge Sort (Optimized)

public void mergeSortInPlace(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSortInPlace(arr, left, mid);
        mergeSortInPlace(arr, mid + 1, right);
        mergeInPlace(arr, left, mid, right);
    }
}

private void mergeInPlace(int[] arr, int left, int mid, int right) {
    int start2 = mid + 1;
    
    // If already sorted, no need to merge
    if (arr[mid] <= arr[start2]) return;
    
    while (left <= mid && start2 <= right) {
        if (arr[left] <= arr[start2]) {
            left++;
        } else {
            int value = arr[start2];
            int index = start2;
            
            // Shift elements right
            while (index != left) {
                arr[index] = arr[index - 1];
                index--;
            }
            arr[left] = value;
            
            left++;
            mid++;
            start2++;
        }
    }
}

Complexity Analysis

Merge Sort for Linked Lists

Merge sort is ideal for linked lists due to:

1. No random access needed (unlike quicksort)
2. O(1) merge (just relink pointers)
3. O(log n) space for recursion stack only

public ListNode mergeSortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    // Find middle using slow/fast pointers
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    ListNode mid = slow.next;
    slow.next = null;  // Split list
    
    // Recursively sort halves
    ListNode left = mergeSortList(head);
    ListNode right = mergeSortList(mid);
    
    // Merge sorted lists
    return mergeLists(left, right);
}

private ListNode mergeLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    current.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

External Merge Sort

Used for sorting files larger than memory:

1. Divide file into chunks that fit in memory
2. Sort each chunk in memory
3. Merge sorted chunks using k-way merge

When to Use Merge Sort

Use when:

• Guaranteed O(n log n) needed
• Stability is required
• Sorting linked lists
• External sorting (large files)

Avoid when:

• Memory is limited (use quicksort in-place)
• Array is nearly sorted (use insertion sort)
• Stability not needed (quicksort may be faster in practice)

Comparison with Other Sorts