Day 6 – Recursive Sorting Techniques: Merge Sort, Quick Sort & Recursive Versions

Today I completed the remaining sorting algorithms, focusing on recursive approaches and divide & conquer strategies. These techniques are fundamental for efficient sorting in both theoretical and practical applications.

---

1. Merge Sort

• Type: Divide and Conquer

• Idea: Recursively divide the array into halves until one element remains. Then, merge the halves in sorted order.

Time & Space Complexity

• Time: O(n log n)

  • T(n) = 2T(n/2) + O(n) — merge step takes linear time

• Space: O(n) — extra array needed for merging

Code:

void merge(vector<int> &a, int low, int mid, int high) {
    vector<int> temp;
    int left = low, right = mid+1;

    while (left <= mid && right <= high) {
        if (a[left] <= a[right]) temp.push_back(a[left++]);
        else temp.push_back(a[right++]);
    }
    while (left <= mid) temp.push_back(a[left++]);
    while (right <= high) temp.push_back(a[right++]);

    for (int i = low; i <= high; i++)
        a[i] = temp[i - low];
}

void mergeSort(vector<int> &a, int low, int high) {
    if (low >= high) return;
    int mid = (low + high) / 2;
    mergeSort(a, low, mid);
    mergeSort(a, mid+1, high);
    merge(a, low, mid, high);
}

---

2. Recursive Bubble Sort

• In each recursive call, bubble the largest element to the end.

Time & Space Complexity:

• Time: O(n²) – same as iterative

• Space: O(n) – due to recursion stack

Optimized Version (with didSwap):

void bubbleRecursive(vector<int> &a, int n) {
    if (n == 1) return;

    bool didSwap = false;
    for (int i = 0; i < n-1; i++) {
        if (a[i] > a[i+1]) {
            swap(a[i], a[i+1]);
            didSwap = true;
        }
    }

    if (!didSwap) return;
    bubbleRecursive(a, n-1);
}

---

3. Recursive Insertion Sort

• Build the sorted array one element at a time recursively.

Time & Space Complexity:

• Time: O(n²) worst, O(n) best

• Space: O(n) — recursion stack

Code:

void insertion_sort(int arr[], int i, int n) {

    // Base Case: i == n.
    if (i == n) return;

    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
        int temp = arr[j - 1];
        arr[j - 1] = arr[j];
        arr[j] = temp;
        j--;
    }

    insertion_sort(arr, i + 1, n);
}

---

4. Quick Sort

• Type: Divide and Conquer

• Picks a pivot, partitions array so elements less than pivot go left, greater go right, and recursively sorts both halves.

Recurrence Relation:

• T(n) = T(k) + T(n - k - 1) + O(n) — partitioning is linear

• for worst f(n)=f(0)+f(n-1) or f(n-1)+f(0)

• for best f(n)=2*f(n/2)

Time Complexity:

Space:

• O(log n) average, O(n) worst (due to recursion)

---

Standard QuickSort Code:

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int> &arr, int low, int high) {
    int pivot = arr[low];
    int i = low;
    int j = high;

    while (i < j) {
        while (arr[i] <= pivot && i <= high - 1) {
            i++;
        }

        while (arr[j] > pivot && j >= low + 1) {
            j--;
        }
        if (i < j) swap(arr[i], arr[j]);
    }
    swap(arr[low], arr[j]);
    return j;
}

void qs(vector<int> &arr, int low, int high) {
    if (low < high) {
        int pIndex = partition(arr, low, high);
        qs(arr, low, pIndex - 1);
        qs(arr, pIndex + 1, high);
    }
}

vector<int> quickSort(vector<int> arr) {
    qs(arr, 0, arr.size() - 1);
    return arr;
}

int main()
{
    vector<int> arr = {4, 6, 2, 5, 7, 9, 1, 3};
    int n = arr.size();
    cout << "Before Using quick Sort: " << endl;
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    arr = quickSort(arr);
    cout << "After Using quick sort: " << "\n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 0;
}

---

The above method is also called Hoare partion method, where pivot is the first element.

Lomuto Partition

• Pivot is last element.

• Partitions in a single pass.

• Simpler, but performs more swaps.

• Time: O(n) for partition step

---

Hoare Partition Scheme

• Picks first element as pivot.

• Uses two pointers from both ends.

• Advantage: Fewer swaps than Lomuto

• Partition Time: O(n)

---

Summary

• Learned and implemented merge sort with its recursive logic

• Explored recursive bubble and insertion sort

• Understood quick sort – standard.

• Compared best vs worst case for each sort and derived recurrences

• Gained clarity on when to prefer merge sort (stable, guaranteed O(n log n)) vs quick sort (faster in practice, but not stable)

Theory still pending — will start that soon alongside coding.