⬇️🔀 Merge Sort

Merge sort is a divide-and-conquer sorting algorithm. It works by recursively splitting the array into halves until each subarray has one element, then repeatedly merging those subarrays in sorted order. The merging step combines two sorted lists into one sorted list by repeatedly taking the smaller front element.

Java Implementation (well-commented)

// MergeSort.java
// Classic top-down merge sort implementation in Java with comments.

public class MergeSort {
    // Public API: sorts the array in ascending order.
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        // Temporary array used during merges
        int[] aux = new int[arr.length];
        mergeSortRecursive(arr, aux, 0, arr.length - 1);
    }

    // Recursively split the array and merge sorted halves.
    private static void mergeSortRecursive(int[] arr, int[] aux, int low, int high) {
        // Base case: single element is already sorted
        if (low >= high) return;

        int mid = low + (high - low) / 2;

        // Sort left half
        mergeSortRecursive(arr, aux, low, mid);

        // Sort right half
        mergeSortRecursive(arr, aux, mid + 1, high);

        // Merge sorted halves [low..mid] and [mid+1..high]
        merge(arr, aux, low, mid, high);
    }

    // Merge two adjacent sorted subarrays into arr.
    // Left:  low..mid, Right: mid+1..high
    private static void merge(int[] arr, int[] aux, int low, int mid, int high) {
        // Copy the range into auxiliary array
        for (int k = low; k <= high; k++) {
            aux[k] = arr[k];
        }

        int i = low;      // pointer in left half
        int j = mid + 1;  // pointer in right half
        int k = low;      // pointer in destination (arr)

        // Merge by taking the smaller of aux[i] and aux[j]
        while (i <= mid && j <= high) {
            if (aux[i] <= aux[j]) {
                arr[k++] = aux[i++];
            } else {
                arr[k++] = aux[j++];
            }
        }

        // If left half has remaining elements, copy them
        while (i <= mid) {
            arr[k++] = aux[i++];
        }

        // Remaining right-half elements (if any) are already in place.
    }

    // Example usage and simple print helper
    public static void printArray(int[] arr) {
        for (int x : arr) {
            System.out.print(x + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before sort:");
        printArray(data);

        mergeSort(data);

        System.out.println("After sort:");
        printArray(data);
    }
}
      

Pros & Cons

Pros: Merge sort has guaranteed O(n log n) time complexity in best, average and worst cases, and is stable (maintains input order for equal elements) when implemented carefully. It performs particularly well on large datasets and when stable sorting is needed.

Cons: It requires additional memory proportional to the array size for the merge step (unless implemented as an in-place variant), which can be a disadvantage in memory-constrained environments.

Best suited for

Merge sort is best for large arrays, data that must be stably sorted, and situations where worst-case performance guarantees are required. It's also suited for external sorting (sorting data that doesn't fit in memory) because merges can be done in streamed fashion.

Quick summary

Merge sort divides the array recursively and merges sorted subarrays. It reliably achieves O(n log n) runtime and produces stable results, at the cost of additional memory for merging.