Sorting Algorithms – QuickSort & MergeSort

Both QuickSort and MergeSort achieve O(n log n) average performance.

• QuickSort – partition array around a pivot, then recursively sort partitions. In‑place, but worst‑case O(n²) if pivot choices are poor.
• MergeSort – divide the array, sort each half, then merge. Guarantees O(n log n) but requires O(n) extra space.

Both are classic examples of divide‑and‑conquer.

---

📚 QuickSort Implementation (Lomuto partition)

void quicksort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quicksort(a, lo, p - 1);
        quicksort(a, p + 1, hi);
    }
}

📚 MergeSort Implementation

void mergesort(int a[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergesort(a, left, mid);
    mergesort(a, mid+1, right);
    merge(a, left, mid, right);
}