Unit 6: Efficient Sorting Algorithms & Analysis

Opening Hook — The Algorithm Behind Every "Sort By" Button

Learning Outcomes — Bloom's Taxonomy Mapped

Concept Explanation — Efficient Sorting from Scratch

1. Introduction to O(n log n) Sorting

In competitive coding, time limits are strict — usually 1–2 seconds. A modern computer executes roughly 10⁸ operations per second. If you use Bubble Sort (O(n²)) on n = 10⁶ elements, you need 10¹² operations — that's 10,000 seconds. You'd get TLE (Time Limit Exceeded) every single time.

Why O(n²) Sorts Fail in Competitive Programming

At n = 10⁶, O(n log n) takes ~0.2 seconds. O(n²) takes ~10,000 seconds. That's the difference between AC (Accepted) and TLE.

2. Iterative Merge Sort (Bottom-Up)

Intuition: Instead of recursively splitting the array, start from the bottom. First merge pairs of single elements, then pairs of size 2, then pairs of size 4, and so on until the whole array is sorted. It's like building a pyramid from the base up.

Step-by-Step Trace: [38, 27, 43, 3, 9, 82, 10]

C++ Implementation

C++
#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> temp;
    int i = l, j = m + 1;
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while (i <= m) temp.push_back(arr[i++]);
    while (j <= r) temp.push_back(arr[j++]);
    for (int k = l; k <= r; k++)
        arr[k] = temp[k - l];
}

void iterativeMergeSort(vector<int>& arr) {
    int n = arr.size();
    // Start with sub-arrays of size 1, double each pass
    for (int size = 1; size < n; size *= 2) {
        for (int left = 0; left < n - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = min(left + 2 * size - 1, n - 1);
            merge(arr, left, mid, right);
        }
    }
}

Python Implementation

Python
def iterative_merge_sort(arr):
    n = len(arr)
    size = 1
    while size < n:
        for left in range(0, n - size, 2 * size):
            mid = left + size - 1
            right = min(left + 2 * size - 1, n - 1)
            # Merge arr[left..mid] and arr[mid+1..right]
            merged = []
            i, j = left, mid + 1
            while i <= mid and j <= right:
                if arr[i] <= arr[j]:
                    merged.append(arr[i]); i += 1
                else:
                    merged.append(arr[j]); j += 1
            while i <= mid:
                merged.append(arr[i]); i += 1
            while j <= right:
                merged.append(arr[j]); j += 1
            arr[left:right+1] = merged
        size *= 2
    return arr

3. Recursive Merge Sort (Top-Down)

Intuition: Imagine you have a deck of unsorted cards. Split the deck in half. Give each half to a friend. Each friend splits their half again and again until they hold just one card (which is trivially sorted). Then everyone merges their sorted halves back together. That's Merge Sort.

Algorithm

1. Divide: Split the array into two halves
2. Conquer: Recursively sort each half
3. Combine: Merge the two sorted halves into one sorted array

Full Recursion Tree: [38, 27, 43, 3, 9, 82, 10]

                    [38, 27, 43, 3, 9, 82, 10]
                   /                            \
          [38, 27, 43, 3]                   [9, 82, 10]
          /            \                    /          \
      [38, 27]      [43, 3]            [9, 82]       [10]
      /     \       /     \            /     \          |
    [38]   [27]   [43]   [3]        [9]    [82]       [10]
      \     /       \     /            \     /          |
      [27, 38]      [3, 43]          [9, 82]         [10]
          \            /                \              /
        [3, 27, 38, 43]                 [9, 10, 82]
                   \                        /
              [3, 9, 10, 27, 38, 43, 82]

The Merge Procedure — Step by Step

Merging [3, 27, 38, 43] and [9, 10, 82]:

C++ Implementation

C++
#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    vector<int> L(n1), R(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, k = l;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    // Copy remaining elements
    while(i < n1) arr[k++] = L[i++];
    while(j < n2) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);       // Sort left half
        mergeSort(arr, m + 1, r);  // Sort right half
        merge(arr, l, m, r);       // Merge sorted halves
    }
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);
    for(int x : arr) cout << x << " ";
    return 0;
}

Python Implementation

Python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))
# Output: [3, 9, 10, 27, 38, 43, 82]

4. Quick Sort

Intuition: Pick one element (the "pivot"). Put all smaller elements to its left and all larger elements to its right. Now the pivot is in its correct sorted position. Recursively do the same for the left and right sub-arrays.

Lomuto Partition Scheme

The simpler scheme: pivot is the last element. Maintain a pointer i that tracks the boundary of "elements ≤ pivot."

Full Trace: [10, 80, 30, 90, 40, 50, 70] — Lomuto, Pivot = 70

After partition: 70 is at index 4 — its correct sorted position. Left sub-array [10,30,40,50] and right sub-array [90,80] are recursively sorted.

Hoare Partition Scheme

Faster in practice: uses two pointers starting from both ends, moving inward. Fewer swaps on average than Lomuto.

C++ — Lomuto Partition + Quick Sort

C++
#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // Pivot = last element
    int i = low - 1;
    for(int j = low; j < high; j++) {
        if(arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

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

int main() {
    vector<int> arr = {10, 80, 30, 90, 40, 50, 70};
    quickSort(arr, 0, arr.size() - 1);
    for(int x : arr) cout << x << " ";
    return 0;
}

C++ — Hoare Partition

C++
int hoarePartition(vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    while(true) {
        do { i++; } while(arr[i] < pivot);
        do { j--; } while(arr[j] > pivot);
        if(i >= j) return j;
        swap(arr[i], arr[j]);
    }
}

Python — Quick Sort

Python
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

arr = [10, 80, 30, 90, 40, 50, 70]
quick_sort(arr, 0, len(arr) - 1)
print(arr)
# Output: [10, 30, 40, 50, 70, 80, 90]

Randomized Quick Sort

To avoid worst case on sorted/reverse-sorted arrays, choose a random pivot:

C++
#include <cstdlib>

int randomPartition(vector<int>& arr, int low, int high) {
    int randIdx = low + rand() % (high - low + 1);
    swap(arr[randIdx], arr[high]); // Move random pivot to end
    return partition(arr, low, high);
}

5. Sorting Elements by Frequency

Intuition: Instead of sorting by value, sort by how often each element appears. Elements that appear more frequently come first. Ties are broken by the value or by order of first appearance.

Algorithm

1. Count frequency of each element using a HashMap
2. Sort using a custom comparator: higher frequency first; if tie, smaller value first

Trace: [2, 5, 2, 8, 5, 6, 8, 8]

Output (sorted by frequency desc, then value asc): [8, 8, 8, 2, 2, 5, 5, 6]

C++ Implementation

C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

void sortByFrequency(vector<int>& arr) {
    unordered_map<int, int> freq;
    for(int x : arr) freq[x]++;

    sort(arr.begin(), arr.end(),
        [&freq](int a, int b) {
            if(freq[a] != freq[b])
                return freq[a] > freq[b]; // Higher freq first
            return a < b;             // Tie: smaller value first
        });
}

int main() {
    vector<int> arr = {2, 5, 2, 8, 5, 6, 8, 8};
    sortByFrequency(arr);
    for(int x : arr) cout << x << " ";
    return 0;
}
// Output: 8 8 8 2 2 5 5 6

Python Implementation

Python
from collections import Counter

def sort_by_frequency(arr):
    freq = Counter(arr)
    return sorted(arr, key=lambda x: (-freq[x], x))

arr = [2, 5, 2, 8, 5, 6, 8, 8]
print(sort_by_frequency(arr))
# Output: [8, 8, 8, 2, 2, 5, 5, 6]

6. Finding Minimum Length Sorted Sub-array

Problem: Given an unsorted array, find the shortest sub-array such that sorting only this sub-array makes the entire array sorted.

Approach (Two Pointers from Both Ends)

1. From left: Find the first element that is smaller than its predecessor → start of unsorted region
2. From right: Find the first element that is larger than its successor → end of unsorted region
3. Find min and max within this sub-array
4. Extend left boundary to include any element > min of sub-array
5. Extend right boundary to include any element < max of sub-array

Trace: [2, 6, 4, 8, 10, 9, 15]

Answer: Sort sub-array from index 1 to 5 → [6, 4, 8, 10, 9] → sorted as [4, 6, 8, 9, 10]. Full array becomes [2, 4, 6, 8, 9, 10, 15]. Length = 5.

C++ Implementation

C++
int findMinSubarray(vector<int>& arr) {
    int n = arr.size();
    int start = -1, end = -1;

    // Find start: first element out of order from left
    for(int i = 0; i < n - 1; i++) {
        if(arr[i] > arr[i + 1]) { start = i; break; }
    }
    if(start == -1) return 0; // Already sorted

    // Find end: first element out of order from right
    for(int i = n - 1; i > 0; i--) {
        if(arr[i] < arr[i - 1]) { end = i; break; }
    }

    // Find min and max in sub-array
    int subMin = *min_element(arr.begin() + start, arr.begin() + end + 1);
    int subMax = *max_element(arr.begin() + start, arr.begin() + end + 1);

    // Extend boundaries
    for(int i = 0; i < start; i++)
        if(arr[i] > subMin) { start = i; break; }
    for(int i = n - 1; i > end; i--)
        if(arr[i] < subMax) { end = i; break; }

    return end - start + 1;
}

Python Implementation

Python
def find_min_subarray(arr):
    n = len(arr)
    start, end = -1, -1

    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            start = i; break
    if start == -1: return 0

    for i in range(n - 1, 0, -1):
        if arr[i] < arr[i - 1]:
            end = i; break

    sub_min = min(arr[start:end + 1])
    sub_max = max(arr[start:end + 1])

    for i in range(start):
        if arr[i] > sub_min:
            start = i; break
    for i in range(n - 1, end, -1):
        if arr[i] < sub_max:
            end = i; break

    return end - start + 1

print(find_min_subarray([2, 6, 4, 8, 10, 9, 15]))
# Output: 5

7. Sorting Strings

Lexicographic Order: Strings are compared character by character from left to right, using their ASCII values. "apple" < "banana" because 'a' (97) < 'b' (98). "app" < "apple" because "app" is a prefix and shorter.

Comparison Functions Across Languages

C++ — Sort Array of Strings

C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"banana", "apple", "cherry",
                              "date", "elderberry"};
    sort(words.begin(), words.end()); // Lexicographic sort
    for(auto& w : words)
        cout << w << " ";
    return 0;
}
// Output: apple banana cherry date elderberry

Python — Sort Strings

Python
words = ["banana", "apple", "cherry", "date", "elderberry"]
words.sort()  # In-place lexicographic sort
print(words)
# Output: ['apple', 'banana', 'cherry', 'date', 'elderberry']

# Sort by string length
words.sort(key=len)
print(words)
# Output: ['date', 'apple', 'banana', 'cherry', 'elderberry']

Time Complexity: O(n · m · log n) where n is the number of strings and m is the average string length.

8. Case-Specific Sorting

Problem: Given a string with uppercase and lowercase letters, sort uppercase and lowercase letters separately, but maintain their original relative positions (uppercase stays where uppercase was, lowercase stays where lowercase was).

Trace: "eDbACa"

C++ Implementation

C++
#include <iostream>
#include <algorithm>
using namespace std;

string caseSort(string s) {
    string lower, upper;
    for(char c : s) {
        if(islower(c)) lower += c;
        else upper += c;
    }
    sort(lower.begin(), lower.end());
    sort(upper.begin(), upper.end());

    int li = 0, ui = 0;
    for(int i = 0; i < s.size(); i++) {
        if(islower(s[i])) s[i] = lower[li++];
        else s[i] = upper[ui++];
    }
    return s;
}

int main() {
    cout << caseSort("eDbACa") << endl;
    return 0;
}
// Output: aAbCeD

Python Implementation

Python
def case_sort(s):
    lower = sorted([c for c in s if c.islower()])
    upper = sorted([c for c in s if c.isupper()])
    li = ui = 0
    result = []
    for c in s:
        if c.islower():
            result.append(lower[li]); li += 1
        else:
            result.append(upper[ui]); ui += 1
    return "".join(result)

print(case_sort("eDbACa"))
# Output: aAbCeD

9. Count Distinct Pairs with Difference of K

Problem: Given an array of integers and an integer k, count the number of distinct pairs (a, b) such that |a − b| = k.

Approach 1: Sort + Two Pointers

1. Sort the array
2. Use two pointers i and j (j > i)
3. If arr[j] − arr[i] == k → count it, advance both
4. If difference < k → advance j
5. If difference > k → advance i

Approach 2: HashSet

1. Insert all elements into a set
2. For each element x, check if (x + k) exists in the set

Trace: arr = [1, 5, 3, 4, 2], k = 3

Sorted: [1, 2, 3, 4, 5]

Answer: 2 pairs → (1,4) and (2,5)

C++ — Sort + Two Pointer

C++
int countPairs(vector<int>& arr, int k) {
    sort(arr.begin(), arr.end());
    int count = 0, i = 0, j = 1;
    int n = arr.size();
    while(j < n) {
        int diff = arr[j] - arr[i];
        if(diff == k) {
            count++;
            i++; j++;
            // Skip duplicates
            while(j < n && arr[j] == arr[j-1]) j++;
        } else if(diff < k) {
            j++;
        } else {
            i++;
            if(i == j) j++;
        }
    }
    return count;
}

Python — HashSet Approach

Python
def count_pairs(arr, k):
    s = set(arr)
    count = 0
    for x in s:
        if x + k in s:
            count += 1
    return count

print(count_pairs([1, 5, 3, 4, 2], 3))
# Output: 2

10. Counting Sort

Intuition: Don't compare elements at all! Instead, count how many times each value appears, then reconstruct the sorted array. It's like having 10 boxes labeled 0–9, dropping each number into its box, then reading boxes left to right.

Algorithm (Step-by-Step)

1. Find the maximum element in the array → determines count array size
2. Create a count array of size (max + 1), initialized to 0
3. Count occurrences: for each element, increment count[element]
4. Compute prefix sums: count[i] += count[i−1] (gives final positions)
5. Build output: traverse input right-to-left, place each element at count[element]−1, decrement count

Full Trace: [4, 2, 2, 8, 3, 3, 1]

Output: [1, 2, 2, 3, 3, 4, 8]

C++ Implementation

C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    vector<int> count(maxVal + 1, 0);
    vector<int> output(arr.size());

    // Count occurrences
    for(int x : arr) count[x]++;

    // Compute prefix sums
    for(int i = 1; i <= maxVal; i++)
        count[i] += count[i - 1];

    // Build output (right to left for stability)
    for(int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    arr = output;
}

int main() {
    vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);
    for(int x : arr) cout << x << " ";
    return 0;
}
// Output: 1 2 2 3 3 4 8

Python Implementation

Python
def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    output = [0] * len(arr)

    for x in arr:
        count[x] += 1

    for i in range(1, max_val + 1):
        count[i] += count[i - 1]

    for x in reversed(arr):
        output[count[x] - 1] = x
        count[x] -= 1

    return output

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))
# Output: [1, 2, 2, 3, 3, 4, 8]

📊 Master Comparison Table

Learn by Doing — 3-Tier Lab Structure

Problem Set — Tracing, Programming & Interview

🔍 Tracing Questions (5)

💻 Programming Questions (8)

🏢 Industry Problems (3)

🎤 Interview Questions (3)

MCQ Assessment Bank — 30 Questions (Bloom's Mapped)

Remember / Identify (Q1–Q5)

Understand / Explain (Q6–Q10)

Apply / Implement (Q11–Q15)

Analyze / Compare (Q16–Q20)

Evaluate / Judge (Q21–Q25)

Create / Design (Q26–Q30)

Short Answer Questions (8)

Long Answer Questions (3)

Lab Programs — Complete Code with Output & Viva

C++
#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[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, k = l;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    while(i < n1) arr[k++] = L[i++];
    while(j < n2) arr[k++] = R[j++];
}

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

void printArray(int arr[], int n) {
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    cout << "Sorted array:   ";
    printArray(arr, n);
    return 0;
}

C++
#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Lomuto: pivot = last element
    int i = low - 1;

    for(int j = low; j < high; j++) {
        if(arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

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

void printArray(int arr[], int n) {
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array:   ";
    printArray(arr, n);
    return 0;
}

C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSort(int arr[], int n) {
    int maxVal = *max_element(arr, arr + n);
    vector<int> count(maxVal + 1, 0);
    vector<int> output(n);

    // Step 1: Count occurrences
    for(int i = 0; i < n; i++)
        count[arr[i]]++;

    // Step 2: Prefix sums
    for(int i = 1; i <= maxVal; i++)
        count[i] += count[i - 1];

    // Step 3: Build output (right to left for stability)
    for(int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Copy back
    for(int i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    countingSort(arr, n);

    cout << "Sorted array:   ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"banana", "apple", "cherry",
                              "date", "elderberry"};

    // Lexicographic sort (default)
    cout << "Original: ";
    for(auto& w : words) cout << w << " ";
    cout << endl;

    sort(words.begin(), words.end());
    cout << "Lexicographic: ";
    for(auto& w : words) cout << w << " ";
    cout << endl;

    // Sort by length
    sort(words.begin(), words.end(),
        [](const string& a, const string& b) {
            if(a.length() != b.length())
                return a.length() < b.length();
            return a < b; // Same length → lexicographic
        });
    cout << "By length:     ";
    for(auto& w : words) cout << w << " ";
    cout << endl;

    // Case-insensitive sort
    vector<string> mixed = {"Banana", "apple", "Cherry", "date"};
    sort(mixed.begin(), mixed.end(),
        [](string a, string b) {
            transform(a.begin(), a.end(), a.begin(), ::tolower);
            transform(b.begin(), b.end(), b.begin(), ::tolower);
            return a < b;
        });
    cout << "Case-insensitive: ";
    for(auto& w : mixed) cout << w << " ";
    cout << endl;

    return 0;
}

Industry Spotlight — A Day in the Life

Earn With It — Freelance & Income Roadmap

⏱️ Time to First Earning: 1–2 weeks (if you sign up on Chegg and start answering sorting-related questions)

Chapter Summary — Key Takeaways

📊 Complete Sorting Algorithm Comparison

Earning Checkpoint — Are You Ready?

✅ Unit 6 complete. Ready for Unit 7: Searching & Hashing!

[QR: Link to EduArtha video tutorial — Sorting Algorithms Masterclass]