Skip to content
DSA sorting 12 min read

Sorting Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the sorting exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and common pitfalls. Try the problems first — then check your work here.

Q1. Implement insertion sort

Idea: Grow a sorted prefix. For each element, shift larger prefix elements one slot right and drop the element into the gap. The strict > test keeps it stable.

Complexity: O(n) best (already sorted), O(n²) average and worst; O(1) space.

void insertionSort(std::vector<int>& a) {
    for (int i = 1; i < (int)a.size(); i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

Pitfall: Using >= instead of > shifts equal elements too, breaking stability and wasting work. Stop the shift as soon as you reach an element that is not strictly greater.

Q2. Sort numbers descending (mind the comparator)

Idea: Pass a descending comparator. In JavaScript the default sort() is the trap: with no comparator it sorts elements as strings, so [10, 2, 1].sort() yields [1, 10, 2]. Always pass (a, b) => b - a for numeric descending order.

Complexity: O(n log n) time; space depends on the library (O(log n)–O(n)).

#include <algorithm>
#include <functional>
#include <vector>

void sortDesc(std::vector<int>& a) {
    std::sort(a.begin(), a.end(), std::greater<int>());
}

Pitfall: arr.sort() in JavaScript and the Java primitive Arrays.sort(int[]) have no notion of “descending.” For JS you must supply a comparator; for Java primitives there is no descending overload — box to Integer[] and use Collections.reverseOrder(), or sort ascending then reverse.

Q3. Sort pairs by score, ties by name

Idea: Use a multi-key comparator: compare by score descending; if equal, by name ascending. A single composite comparator handles both keys in one pass.

Complexity: O(n log n) time, O(1)–O(n) space depending on the sort.

struct Rec { std::string name; int score; };

void sortRecs(std::vector<Rec>& v) {
    std::sort(v.begin(), v.end(), [](const Rec& a, const Rec& b) {
        if (a.score != b.score) return a.score > b.score; // score desc
        return a.name < b.name;                           // name asc
    });
}

Pitfall: Doing two separate sorts in the wrong order, or relying on stability without it being guaranteed. C++ std::sort is not stable, so encode all tie-breakers in the comparator rather than assuming equal elements keep their order.

Q4. Merge two sorted arrays

Idea: Two pointers, one per array. Repeatedly append the smaller front element; when one array is exhausted, append the rest of the other. Single linear pass.

Complexity: O(n + m) time, O(n + m) space for the output.

std::vector<int> merge(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> out;
    out.reserve(a.size() + b.size());
    size_t i = 0, j = 0;
    while (i < a.size() && j < b.size())
        out.push_back(a[i] <= b[j] ? a[i++] : b[j++]);
    while (i < a.size()) out.push_back(a[i++]);
    while (j < b.size()) out.push_back(b[j++]);
    return out;
}

Pitfall: Forgetting to drain the remaining elements after one array runs out — the two trailing while loops are essential. Use <= (not <) when picking to keep the merge stable.

Q5. Counting sort for a bounded range

Idea: Tally each value into a count array of size k + 1, then walk the counts in order, emitting each value the number of times it appeared. No comparisons.

Complexity: O(n + k) time, O(n + k) space.

std::vector<int> countingSort(const std::vector<int>& a, int k) {
    std::vector<int> count(k + 1, 0), out;
    out.reserve(a.size());
    for (int x : a) count[x]++;
    for (int v = 0; v <= k; v++)
        while (count[v]-- > 0) out.push_back(v);
    return out;
}

Pitfall: Counting sort is only efficient when k is on the order of n. If values span a huge range (or aren’t small integers), use radix sort or a comparison sort instead — a count array sized to a billion is not viable.

Q6. Kth largest element

Idea: Sorting gives O(n log n). For average O(n), use quickselect: partition around a random pivot like quick sort, but recurse into only the side that contains the target index n - k (the position of the k-th largest in ascending order).

Complexity: O(n) average, O(n²) worst (mitigated by a random pivot); O(1) extra space.

int kthLargest(std::vector<int> a, int k) {
    int target = (int)a.size() - k, lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        std::swap(a[lo + rand() % (hi - lo + 1)], a[hi]); // random pivot
        int pivot = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < pivot) std::swap(a[i++], a[j]);
        std::swap(a[i], a[hi]);
        if (i == target) return a[i];
        if (i < target) lo = i + 1; else hi = i - 1;
    }
    return -1; // unreachable for valid k
}

Pitfall: Mixing up “k-th largest” with index k. The k-th largest sits at ascending index n - k (so k = 1 maps to index n - 1, the maximum). A fixed (non-random) pivot makes sorted input degrade to O(n²) — randomize it.

Q7. Sort colors (Dutch national flag)

Idea: Three pointers in one pass: low (next 0 slot), high (next 2 slot), and mid (scanner). Push 0s to the front and 2s to the back; 1s fall into place in the middle. When you swap a 2 in from high, don’t advance mid — the swapped-in value is unexamined.

Complexity: O(n) time, O(1) space, single pass.

void sortColors(std::vector<int>& a) {
    int low = 0, mid = 0, high = (int)a.size() - 1;
    while (mid <= high) {
        if (a[mid] == 0) std::swap(a[low++], a[mid++]);
        else if (a[mid] == 1) mid++;
        else std::swap(a[mid], a[high--]); // a[mid]==2; don't advance mid
    }
}

Pitfall: Advancing mid after swapping with high. The element pulled in from high hasn’t been classified yet, so you must re-examine it on the next iteration — only advance mid for the 0 and 1 cases.

That’s the full answer sheet. Back to the sorting exercises or continue to Searching.

Last updated June 25, 2026
Was this helpful?