Merge Sort and Quick Sort

These are advanced, highly efficient sorting algorithms based on the Divide and Conquer paradigm.

1. Merge Sort

Merge Sort divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

• Time Complexity: O(n log n) in all cases.
• Space Complexity: O(n) (requires extra space for merging).

Merge Sort Java Implementation

public class MergeSort {
    void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }

    void sort(int arr[], int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }
}

2. Quick Sort

Quick Sort picks an element as a pivot and partitions the given array around the picked pivot. The elements smaller than the pivot go to the left, and elements greater go to the right.

• Time Complexity: Average/Best O(n log n), Worst O(n^2) (if already sorted and pivot is extreme; typically avoided with randomized pivot).
• Space Complexity: O(log n) call stack.

Quick Sort Java Implementation

public class QuickSort {
    int partition(int arr[], int low, int high) {
        int pivot = arr[high]; 
        int i = (low - 1); // index of smaller element
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    void sort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }
}