Step 5 of 7

71% Complete

Merge Sort

Learn the stable, guaranteed O(n log n) sorting algorithm: Merge Sort

What is Merge Sort?

Merge Sort is a stable, divide-and-conquer sorting algorithm that divides the array into smaller sub-arrays, recursively sorts them, and then merges them back together. It guarantees O(n log n) performance even in the worst case.

While it requires O(n) extra space, its guaranteed performance and stability make it ideal for scenarios where worst-case performance is critical.

How Merge Sort Works

The Divide-and-Conquer Process

Divide: Split the array in half repeatedly until subarrays of size 1
Conquer: Arrays of size 1 are already sorted
Merge: Merge two sorted subarrays into one sorted array
Repeat: Continue merging until single sorted array remains

Merge Sort - Visual Example

// Initial array: [38, 27, 43, 3, 9, 82, 10]
 
// Divide:
// [38, 27, 43, 3] [9, 82, 10]
// [38, 27] [43, 3] [9, 82] [10]
// [38] [27] [43] [3] [9] [82] [10]
 
// Merge (combining sorted subarrays):
// [27, 38] [3, 43] [9, 82] [10]
// [3, 27, 38, 43] [9, 10, 82]
// [3, 9, 10, 27, 38, 43, 82]

The Merge Operation

The merge operation is the key to Merge Sort. It takes two sorted arrays and combines them into one sorted array efficiently.

Merging Two Sorted Arrays

// Two sorted arrays:
// Left: [3, 27, 38, 43]
// Right: [9, 10, 82]
 
// Merge process:
// Compare 3 and 9 → Add 3 to result
// Compare 27 and 9 → Add 9 to result
// Compare 27 and 10 → Add 10 to result
// Compare 27 and 82 → Add 27 to result
// Compare 38 and 82 → Add 38 to result
// Compare 43 and 82 → Add 43 to result
// Add remaining 82
 
// Result: [3, 9, 10, 27, 38, 43, 82]

Implementation

Merge Sort Implementation

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr.length == 0) return;
        mergeSort(arr, 0, arr.length - 1);
    }
    
    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            // Recursively sort left half
            mergeSort(arr, left, mid);
            
            // Recursively sort right half
            mergeSort(arr, mid + 1, right);
            
            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        // Create temporary arrays
        int[] leftArr = new int[mid - left + 1];
        int[] rightArr = new int[right - mid];
        
        // Copy data to temp arrays
        System.arraycopy(arr, left, leftArr, 0, leftArr.length);
        System.arraycopy(arr, mid + 1, rightArr, 0, rightArr.length);
        
        // Merge the temp arrays
        int i = 0, j = 0, k = left;
        
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }
        
        // Copy remaining elements from left array
        while (i < leftArr.length) {
            arr[k++] = leftArr[i++];
        }
        
        // Copy remaining elements from right array
        while (j < rightArr.length) {
            arr[k++] = rightArr[j++];
        }
    }
    
    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 90};
        mergeSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Output: [11, 12, 22, 25, 34, 64, 90]
    }
}

Space-Optimized Merge Sort

We can reduce unnecessary array allocations by creating the auxiliary arrays once at the start.

Optimized Merge Sort

public class MergeSortOptimized {
    private int[] temp;
    
    public void mergeSort(int[] arr) {
        temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1);
    }
    
    private void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    private void merge(int[] arr, int left, int mid, int right) {
        // Copy all elements to temp array
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }
        
        int i = left, j = mid + 1, k = left;
        
        // Merge back to original array
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k++] = temp[i++];
            } else {
                arr[k++] = temp[j++];
            }
        }
        
        // Copy remaining elements
        while (i <= mid) {
            arr[k++] = temp[i++];
        }
        while (j <= right) {
            arr[k++] = temp[j++];
        }
    }
}

Time & Space Complexity

Time Complexity

Best: O(n log n)

Average: O(n log n)

Worst: O(n log n)

Space Complexity

O(n) - Auxiliary arrays for merging

Not in-place, but guaranteed performance

Why Always O(n log n)?

The array is divided into halves log n times. Each level requires n comparisons to merge. Total: n × log n = O(n log n). Unlike Quick Sort, this holds even in worst case.

Characteristics

✓ Stable: Maintains order of equal elements

✗ Not in-place: Requires O(n) extra space

✓ Guaranteed: Always O(n log n)

✓ Parallelizable: Good for multi-threading

When to Use Merge Sort

Good for:

When guaranteed O(n log n) performance is required
Stable sorting is needed (e.g., sorting database records)
Sorting linked lists (external sorting preferred)
Large datasets where worst-case matters
Multi-threaded sorting (easily parallelizable)

Avoid for:

Memory-constrained systems (uses O(n) extra space)
Small arrays where overhead matters (use Insertion Sort)
When in-place sorting is required

Merge Sort vs Quick Sort

Why use Merge Sort over Quick Sort?

Guaranteed performance: Always O(n log n), no worst case O(n²)
Stability: Preserves order of equal elements
Parallelization: Easily divides into independent sub-problems
External sorting: Works well with disk-based data

Key Takeaways

Merge Sort guarantees O(n log n) performance in all cases
Stable sorting preserves order of equal elements
Trade-off: Uses O(n) extra space for guaranteed performance
Excellent choice when worst-case performance matters
Works efficiently with external data and multi-threading
Used in databases, file systems, and distributed systems