Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Introduction to Sorting

Editorial

Sorting by two keys

A class list is in name order, and you want it by grade, with each grade's students still in name order. Sorting by grade alone should do it, since the names are already in order. Run on 200 students, comparing grades only:

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

int main() {
    vector<pair<string, int>> students;          // (name, grade), in name order
    for (int i = 0; i < 200; i++) {
        char name[8];
        snprintf(name, sizeof name, "s%03d", i);
        students.push_back({name, i * 37 % 5});
    }
    sort(students.begin(), students.end(),        // by grade only
         [](const auto& a, const auto& b) { return a.second < b.second; });
    int out = 0;
    for (int i = 1; i < 200; i++)
        out += students[i].second == students[i - 1].second && students[i].first < students[i - 1].first;
    printf("grade-mates out of name order: %d of 195\n", out);
}

// grade-mates out of name order: 93 of 195
students = [(f"s{i:03d}", i * 37 % 5) for i in range(200)]   # (name, grade), in name order
students.sort(key=lambda s: s[1])                                # by grade only
out = sum(1 for a, b in zip(students, students[1:]) if a[1] == b[1] and a[0] > b[0])
print(f"grade-mates out of name order: {out} of 195")

# grade-mates out of name order: 0 of 195
import java.util.*;

public class Main {
    record Student(String name, int grade) {}

    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();      // in name order
        for (int i = 0; i < 200; i++) students.add(new Student(String.format("s%03d", i), i * 37 % 5));
        students.sort(Comparator.comparingInt(Student::grade));   // by grade only
        int out = 0;
        for (int i = 1; i < 200; i++)
            if (students.get(i).grade() == students.get(i - 1).grade()
                    && students.get(i).name().compareTo(students.get(i - 1).name()) < 0) out++;
        System.out.println("grade-mates out of name order: " + out + " of 195");
    }
}

// grade-mates out of name order: 0 of 195
const students = Array.from({ length: 200 }, (_, i) =>   // in name order
    ({ name: "s" + String(i).padStart(3, "0"), grade: i * 37 % 5 }));
students.sort((a, b) => a.grade - b.grade);              // by grade only
let out = 0;
for (let i = 1; i < 200; i++)
    if (students[i].grade === students[i - 1].grade && students[i].name < students[i - 1].name) out++;
console.log(`grade-mates out of name order: ${out} of 195`);

// grade-mates out of name order: 0 of 195

Python, Java and JavaScript kept every grade's names in order. C++'s std::sort left 93 of the 195 neighbouring grade-mates out of name order: it compared only grades, as asked, and moved equal grades wherever its partitioning took them.

A sort that keeps equal keys in the order they arrived is stable. Python's sort is, Java's sort of objects is, JavaScript's is, and C++ has std::stable_sort for it. This lesson is about that kind of property: what a sort promises, what it costs in comparisons and moves, and what sorted order buys you, from the three simple sorts up to the library sort in each language.

A dashed band, in name order: six tiles, Ana, Ben, Cai, Dev, Eve and Fay, with grade B, A, B, A, B and A under them, the A tiles blue and the B tiles orange. Arrows down, with the pill sort by grade only, to two dashed panels. Left, ticked, insertion sort: stable: row A, Ben, Dev, Fay; row B, Ana, Cai, Eve; each grade's names in order. Right, crossed, selection sort: not stable: row A, Ben, Dev, Fay; row B, Ana, Eve, Cai, with Eve and Cai ringed in red; a long swap put Eve before Cai. Focal line: stable: equal keys keep the order they came in. Title: equal keys keep their order.

What sorted order buys

Once values are in order, equal ones sit together and every value's neighbours are the values closest to it. Many problems become a scan. Rank Transform of an Array replaces each value by its rank among the distinct values, 1 for the smallest: sort a copy, keep each value once, and a value's rank is its position in that list plus one:

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

vector<int> rankTransform(const vector<int>& arr) {   // each value's rank among the distinct ones, 1 for the smallest
    vector<int> order = arr;
    sort(order.begin(), order.end());
    order.erase(unique(order.begin(), order.end()), order.end());   // sorted, each value once
    vector<int> ranks;
    for (int v : arr) ranks.push_back(lower_bound(order.begin(), order.end(), v) - order.begin() + 1);
    return ranks;
}

int main() {
    for (const auto& arr : vector<vector<int>>{{20, 15, 26, 2, 98, 6}, {10, 10, 5}, {}}) {
        vector<int> r = rankTransform(arr);
        if (r.empty()) printf("(empty)");
        for (size_t i = 0; i < r.size(); i++) printf(i ? " %d" : "%d", r[i]);
        printf("\n");
    }
}

// 4 3 5 1 6 2
// 2 2 1
// (empty)
def rank_transform(arr):              # each value's rank among the distinct ones, 1 for the smallest
    order = sorted(set(arr))          # sorted, each value once
    rank = {v: r + 1 for r, v in enumerate(order)}
    return [rank[v] for v in arr]


for arr in ([20, 15, 26, 2, 98, 6], [10, 10, 5], []):
    print(" ".join(map(str, rank_transform(arr))) or "(empty)")

# 4 3 5 1 6 2
# 2 2 1
# (empty)
import java.util.*;

public class Main {
    static int[] rankTransform(int[] arr) {     // each value's rank among the distinct ones, 1 for the smallest
        int[] order = Arrays.stream(arr).distinct().sorted().toArray();   // sorted, each value once
        int[] ranks = new int[arr.length];
        for (int i = 0; i < arr.length; i++) ranks[i] = Arrays.binarySearch(order, arr[i]) + 1;
        return ranks;
    }

    public static void main(String[] args) {
        for (int[] arr : new int[][]{{20, 15, 26, 2, 98, 6}, {10, 10, 5}, {}}) {
            StringJoiner line = new StringJoiner(" ");
            for (int r : rankTransform(arr)) line.add(String.valueOf(r));
            System.out.println(line.length() > 0 ? line.toString() : "(empty)");
        }
    }
}

// 4 3 5 1 6 2
// 2 2 1
// (empty)
function rankTransform(arr) {             // each value's rank among the distinct ones, 1 for the smallest
    const order = [...new Set(arr)].sort((a, b) => a - b);   // sorted, each value once
    const rank = new Map(order.map((v, r) => [v, r + 1]));
    return arr.map((v) => rank.get(v));
}

for (const arr of [[20, 15, 26, 2, 98, 6], [10, 10, 5], []])
    console.log(rankTransform(arr).join(" ") || "(empty)");

// 4 3 5 1 6 2
// 2 2 1
// (empty)

The sort is O(n log n), and the look-ups after it are O(1) with a map or O(log n) with binary search, so the whole thing is O(n log n), where comparing every value with every other is O(n²). The same trade runs through the course: duplicates found side by side (Hashing does it without sorting), two pointers closing in from both ends of a sorted array (Two Pointers), binary search (Binary Search), and intervals merged in order of their starts (Intervals).

Three simple sorts

Each of the three keeps a sorted part and grows it by one value a pass. They differ in how they find that value and how they make room for it. On the same six values, each printing what it did:

Selection sort finds the smallest value not yet placed and swaps it into the next place:

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

void show(const string& label, const vector<int>& a) {
    printf("%s:", label.c_str());
    for (int v : a) printf(" %d", v);
    printf("\n");
}

void selectionSort(vector<int>& a) {         // pass i: find the smallest of a[i..], swap it to i
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[smallest]) smallest = j;
        swap(a[i], a[smallest]);
        show("pass " + to_string(i + 1), a);
    }
}

int main() {
    vector<int> a = {5, 2, 4, 6, 1, 3};
    selectionSort(a);
}

// pass 1: 1 2 4 6 5 3
// pass 2: 1 2 4 6 5 3
// pass 3: 1 2 3 6 5 4
// pass 4: 1 2 3 4 5 6
// pass 5: 1 2 3 4 5 6
def selection_sort(a):                # pass i: find the smallest of a[i:], swap it to i
    n = len(a)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]
        print(f"pass {i + 1}:", *a)


selection_sort([5, 2, 4, 6, 1, 3])

# pass 1: 1 2 4 6 5 3
# pass 2: 1 2 4 6 5 3
# pass 3: 1 2 3 6 5 4
# pass 4: 1 2 3 4 5 6
# pass 5: 1 2 3 4 5 6
public class Main {
    static void show(String label, int[] a) {
        StringBuilder line = new StringBuilder(label + ":");
        for (int v : a) line.append(" ").append(v);
        System.out.println(line);
    }

    static void selectionSort(int[] a) {   // pass i: find the smallest of a[i..], swap it to i
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            int smallest = i;
            for (int j = i + 1; j < n; j++)
                if (a[j] < a[smallest]) smallest = j;
            int t = a[i];
            a[i] = a[smallest];
            a[smallest] = t;
            show("pass " + (i + 1), a);
        }
    }

    public static void main(String[] args) {
        selectionSort(new int[]{5, 2, 4, 6, 1, 3});
    }
}

// pass 1: 1 2 4 6 5 3
// pass 2: 1 2 4 6 5 3
// pass 3: 1 2 3 6 5 4
// pass 4: 1 2 3 4 5 6
// pass 5: 1 2 3 4 5 6
function selectionSort(a) {               // pass i: find the smallest of a[i..], swap it to i
    const n = a.length;
    for (let i = 0; i < n - 1; i++) {
        let smallest = i;
        for (let j = i + 1; j < n; j++)
            if (a[j] < a[smallest]) smallest = j;
        [a[i], a[smallest]] = [a[smallest], a[i]];
        console.log(`pass ${i + 1}: ${a.join(" ")}`);
    }
}

selectionSort([5, 2, 4, 6, 1, 3]);

// pass 1: 1 2 4 6 5 3
// pass 2: 1 2 4 6 5 3
// pass 3: 1 2 3 6 5 4
// pass 4: 1 2 3 4 5 6
// pass 5: 1 2 3 4 5 6

Bubble sort walks the unsorted part, swapping each pair of neighbours that's out of order, so the largest value sinks to the end of each pass. A pass with no swap means the list is sorted, and the sort stops:

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

void show(const string& label, const vector<int>& a) {
    printf("%s:", label.c_str());
    for (int v : a) printf(" %d", v);
    printf("\n");
}

void bubbleSort(vector<int>& a) {            // swap neighbours out of order; the largest sinks to the end
    int n = a.size();
    for (int end = n - 1; end > 0; end--) {
        bool swapped = false;
        for (int j = 0; j < end; j++)
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        show("pass " + to_string(n - end), a);
        if (!swapped) break;                  // no swap: already sorted
    }
}

int main() {
    vector<int> a = {5, 2, 4, 6, 1, 3};
    bubbleSort(a);
}

// pass 1: 2 4 5 1 3 6
// pass 2: 2 4 1 3 5 6
// pass 3: 2 1 3 4 5 6
// pass 4: 1 2 3 4 5 6
// pass 5: 1 2 3 4 5 6
def bubble_sort(a):                   # swap neighbours out of order; the largest sinks to the end
    n = len(a)
    for end in range(n - 1, 0, -1):
        swapped = False
        for j in range(end):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        print(f"pass {n - end}:", *a)
        if not swapped:               # no swap: already sorted
            break


bubble_sort([5, 2, 4, 6, 1, 3])

# pass 1: 2 4 5 1 3 6
# pass 2: 2 4 1 3 5 6
# pass 3: 2 1 3 4 5 6
# pass 4: 1 2 3 4 5 6
# pass 5: 1 2 3 4 5 6
public class Main {
    static void show(String label, int[] a) {
        StringBuilder line = new StringBuilder(label + ":");
        for (int v : a) line.append(" ").append(v);
        System.out.println(line);
    }

    static void bubbleSort(int[] a) {      // swap neighbours out of order; the largest sinks to the end
        int n = a.length;
        for (int end = n - 1; end > 0; end--) {
            boolean swapped = false;
            for (int j = 0; j < end; j++)
                if (a[j] > a[j + 1]) {
                    int t = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = t;
                    swapped = true;
                }
            show("pass " + (n - end), a);
            if (!swapped) break;           // no swap: already sorted
        }
    }

    public static void main(String[] args) {
        bubbleSort(new int[]{5, 2, 4, 6, 1, 3});
    }
}

// pass 1: 2 4 5 1 3 6
// pass 2: 2 4 1 3 5 6
// pass 3: 2 1 3 4 5 6
// pass 4: 1 2 3 4 5 6
// pass 5: 1 2 3 4 5 6
function bubbleSort(a) {                  // swap neighbours out of order; the largest sinks to the end
    const n = a.length;
    for (let end = n - 1; end > 0; end--) {
        let swapped = false;
        for (let j = 0; j < end; j++)
            if (a[j] > a[j + 1]) {
                [a[j], a[j + 1]] = [a[j + 1], a[j]];
                swapped = true;
            }
        console.log(`pass ${n - end}: ${a.join(" ")}`);
        if (!swapped) break;                  // no swap: already sorted
    }
}

bubbleSort([5, 2, 4, 6, 1, 3]);

// pass 1: 2 4 5 1 3 6
// pass 2: 2 4 1 3 5 6
// pass 3: 2 1 3 4 5 6
// pass 4: 1 2 3 4 5 6
// pass 5: 1 2 3 4 5 6

Pass 4 left the values in order, and pass 5 found nothing to swap, which is what stops the sort: on values that start in order, the first pass stops it.

Insertion sort takes the next value and shifts every bigger value before it one place right, then drops the value into the gap, the way you'd sort a hand of cards:

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

void show(const string& label, const vector<int>& a) {
    printf("%s:", label.c_str());
    for (int v : a) printf(" %d", v);
    printf("\n");
}

void insertionSort(vector<int>& a) {         // take a[i], shift the bigger values before it one place right
    for (int i = 1; i < (int) a.size(); i++) {
        int key = a[i], j = i;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = key;
        show("insert " + to_string(key), a);
    }
}

int main() {
    vector<int> a = {5, 2, 4, 6, 1, 3};
    insertionSort(a);
}

// insert 2: 2 5 4 6 1 3
// insert 4: 2 4 5 6 1 3
// insert 6: 2 4 5 6 1 3
// insert 1: 1 2 4 5 6 3
// insert 3: 1 2 3 4 5 6
def insertion_sort(a):                # take a[i], shift the bigger values before it one place right
    for i in range(1, len(a)):
        key, j = a[i], i
        while j > 0 and a[j - 1] > key:
            a[j] = a[j - 1]
            j -= 1
        a[j] = key
        print(f"insert {key}:", *a)


insertion_sort([5, 2, 4, 6, 1, 3])

# insert 2: 2 5 4 6 1 3
# insert 4: 2 4 5 6 1 3
# insert 6: 2 4 5 6 1 3
# insert 1: 1 2 4 5 6 3
# insert 3: 1 2 3 4 5 6
public class Main {
    static void show(String label, int[] a) {
        StringBuilder line = new StringBuilder(label + ":");
        for (int v : a) line.append(" ").append(v);
        System.out.println(line);
    }

    static void insertionSort(int[] a) {   // take a[i], shift the bigger values before it one place right
        for (int i = 1; i < a.length; i++) {
            int key = a[i], j = i;
            while (j > 0 && a[j - 1] > key) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = key;
            show("insert " + key, a);
        }
    }

    public static void main(String[] args) {
        insertionSort(new int[]{5, 2, 4, 6, 1, 3});
    }
}

// insert 2: 2 5 4 6 1 3
// insert 4: 2 4 5 6 1 3
// insert 6: 2 4 5 6 1 3
// insert 1: 1 2 4 5 6 3
// insert 3: 1 2 3 4 5 6
function insertionSort(a) {               // take a[i], shift the bigger values before it one place right
    for (let i = 1; i < a.length; i++) {
        const key = a[i];
        let j = i;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = key;
        console.log(`insert ${key}: ${a.join(" ")}`);
    }
}

insertionSort([5, 2, 4, 6, 1, 3]);

// insert 2: 2 5 4 6 1 3
// insert 4: 2 4 5 6 1 3
// insert 6: 2 4 5 6 1 3
// insert 1: 1 2 4 5 6 3
// insert 3: 1 2 3 4 5 6
Three dashed bands, each a row of six tiles before and after one pass, with the sorted part in green. Selection sort, pass 1: 5 2 4 6 1 3 with 1 ringed in orange and an arrow under the row from 1 to the front, then 1 2 4 6 5 3 with 1 green; find the smallest, 1, and swap it to the front. Bubble sort, pass 1: 5 2 4 6 1 3 with 6 ringed and an arrow to the end, then 2 4 5 1 3 6 with 6 green; swap each pair out of order: 6 sinks to the end. Insertion sort, inserting 1: 2 4 5 6 1 3 with 2 4 5 6 green and 1 ringed, an arrow from 1 to the front, then 1 2 4 5 6 3 with the first five green; shift the bigger values right, drop 1 in the gap. Focal line: every pass grows the sorted part by one value. Title: three ways to grow the sorted part.

Comparisons and moves

All three are O(n²), but they spend it differently. Counting every comparison and every swap or shift on 1,000 values, sorted, shuffled and reversed (the shuffle is the same in all four languages, so the counts are too):

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

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}

using Count = pair<long long, long long>;    // (comparisons, swaps or shifts)

Count selection(vector<int>& a) {
    long long comps = 0, moves = 0;
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < n; j++) {
            comps++;
            if (a[j] < a[smallest]) smallest = j;
        }
        if (smallest != i) { swap(a[i], a[smallest]); moves++; }
    }
    return {comps, moves};
}

Count bubble(vector<int>& a, bool early) {
    long long comps = 0, moves = 0;
    for (int end = a.size() - 1; end > 0; end--) {
        bool swapped = false;
        for (int j = 0; j < end; j++) {
            comps++;
            if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); moves++; swapped = true; }
        }
        if (early && !swapped) break;
    }
    return {comps, moves};
}

Count insertion(vector<int>& a, int gap) {   // gap 1 is insertion sort; Shell sort runs it for shrinking gaps
    long long comps = 0, moves = 0;
    for (int i = gap; i < (int) a.size(); i++) {
        int key = a[i], j = i;
        while (j >= gap) {
            comps++;
            if (a[j - gap] <= key) break;
            a[j] = a[j - gap];
            moves++;
            j -= gap;
        }
        a[j] = key;
    }
    return {comps, moves};
}

Count shell(vector<int>& a) {
    Count total = {0, 0};
    for (int gap = a.size() / 2; gap > 0; gap /= 2) {
        Count c = insertion(a, gap);
        total = {total.first + c.first, total.second + c.second};
    }
    return total;
}

int main() {
    int n = 1000;
    vector<int> up(n), down(n);
    for (int i = 0; i < n; i++) up[i] = i, down[i] = n - 1 - i;
    vector<pair<string, vector<int>>> inputs = {{"sorted", up}, {"shuffled", shuffled(n)}, {"reversed", down}};
    vector<pair<string, function<Count(vector<int>&)>>> sorts = {
        {"selection", selection},
        {"bubble", [](vector<int>& a) { return bubble(a, true); }},
        {"bubble, no early exit", [](vector<int>& a) { return bubble(a, false); }},
        {"insertion", [](vector<int>& a) { return insertion(a, 1); }},
        {"shell", shell}};
    for (auto& sort : sorts) {
        printf("%s:", sort.first.c_str());
        for (size_t k = 0; k < inputs.size(); k++) {
            vector<int> a = inputs[k].second;
            Count c = sort.second(a);
            if (!is_sorted(a.begin(), a.end())) return 1;
            printf("%s %s %lld/%lld", k ? "," : "", inputs[k].first.c_str(), c.first, c.second);
        }
        printf("\n");
    }
}

// selection: sorted 499500/0, shuffled 499500/995, reversed 499500/500
// bubble: sorted 999/0, shuffled 499409/248463, reversed 499500/499500
// bubble, no early exit: sorted 499500/0, shuffled 499500/248463, reversed 499500/499500
// insertion: sorted 999/0, shuffled 249457/248463, reversed 499500/499500
// shell: sorted 8006/0, shuffled 15226/7725, reversed 11716/4700
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums


def selection(a):                     # each returns (comparisons, swaps or shifts)
    comps = moves = 0
    n = len(a)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            comps += 1
            if a[j] < a[smallest]:
                smallest = j
        if smallest != i:
            a[i], a[smallest] = a[smallest], a[i]
            moves += 1
    return comps, moves


def bubble(a, early=True):
    comps = moves = 0
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for j in range(end):
            comps += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                moves += 1
                swapped = True
        if early and not swapped:
            break
    return comps, moves


def insertion(a, gap=1):              # gap 1 is insertion sort; Shell sort runs it for shrinking gaps
    comps = moves = 0
    for i in range(gap, len(a)):
        key, j = a[i], i
        while j >= gap:
            comps += 1
            if a[j - gap] <= key:
                break
            a[j] = a[j - gap]
            moves += 1
            j -= gap
        a[j] = key
    return comps, moves


def shell(a):
    comps = moves = 0
    gap = len(a) // 2
    while gap > 0:
        c, m = insertion(a, gap)
        comps, moves = comps + c, moves + m
        gap //= 2
    return comps, moves


n = 1000
inputs = {"sorted": list(range(n)), "shuffled": shuffled(n), "reversed": list(range(n - 1, -1, -1))}
sorts = {"selection": selection, "bubble": bubble, "bubble, no early exit": lambda a: bubble(a, False),
         "insertion": insertion, "shell": shell}
for name, sort_it in sorts.items():
    cells = []
    for kind, values in inputs.items():
        a = values[:]
        comps, moves = sort_it(a)
        assert a == sorted(values)
        cells.append(f"{kind} {comps}/{moves}")
    print(f"{name}: " + ", ".join(cells))

# selection: sorted 499500/0, shuffled 499500/995, reversed 499500/500
# bubble: sorted 999/0, shuffled 499409/248463, reversed 499500/499500
# bubble, no early exit: sorted 499500/0, shuffled 499500/248463, reversed 499500/499500
# insertion: sorted 999/0, shuffled 249457/248463, reversed 499500/499500
# shell: sorted 8006/0, shuffled 15226/7725, reversed 11716/4700
import java.util.*;
import java.util.function.*;

public class Main {
    static int seed = (int) 2463534242L;

    static int randomBelow(int bound) {          // xorshift: the same numbers in every language
        seed ^= seed << 13;
        seed ^= seed >>> 17;
        seed ^= seed << 5;
        return Integer.remainderUnsigned(seed, bound);
    }

    static int[] shuffled(int n) {               // 0 .. n-1 in a random order
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = randomBelow(i + 1), t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

    // each returns {comparisons, swaps or shifts}
    static long[] selection(int[] a) {
        long comps = 0, moves = 0;
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            int smallest = i;
            for (int j = i + 1; j < n; j++) {
                comps++;
                if (a[j] < a[smallest]) smallest = j;
            }
            if (smallest != i) {
                int t = a[i]; a[i] = a[smallest]; a[smallest] = t;
                moves++;
            }
        }
        return new long[]{comps, moves};
    }

    static long[] bubble(int[] a, boolean early) {
        long comps = 0, moves = 0;
        for (int end = a.length - 1; end > 0; end--) {
            boolean swapped = false;
            for (int j = 0; j < end; j++) {
                comps++;
                if (a[j] > a[j + 1]) {
                    int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                    moves++;
                    swapped = true;
                }
            }
            if (early && !swapped) break;
        }
        return new long[]{comps, moves};
    }

    static long[] insertion(int[] a, int gap) {   // gap 1 is insertion sort; Shell sort runs it for shrinking gaps
        long comps = 0, moves = 0;
        for (int i = gap; i < a.length; i++) {
            int key = a[i], j = i;
            while (j >= gap) {
                comps++;
                if (a[j - gap] <= key) break;
                a[j] = a[j - gap];
                moves++;
                j -= gap;
            }
            a[j] = key;
        }
        return new long[]{comps, moves};
    }

    static long[] shell(int[] a) {
        long[] total = {0, 0};
        for (int gap = a.length / 2; gap > 0; gap /= 2) {
            long[] c = insertion(a, gap);
            total[0] += c[0];
            total[1] += c[1];
        }
        return total;
    }

    public static void main(String[] args) {
        int n = 1000;
        int[] up = new int[n], down = new int[n];
        for (int i = 0; i < n; i++) { up[i] = i; down[i] = n - 1 - i; }
        Map<String, int[]> inputs = new LinkedHashMap<>();
        inputs.put("sorted", up);
        inputs.put("shuffled", shuffled(n));
        inputs.put("reversed", down);
        Map<String, Function<int[], long[]>> sorts = new LinkedHashMap<>();
        sorts.put("selection", Main::selection);
        sorts.put("bubble", a -> bubble(a, true));
        sorts.put("bubble, no early exit", a -> bubble(a, false));
        sorts.put("insertion", a -> insertion(a, 1));
        sorts.put("shell", Main::shell);
        for (var sort : sorts.entrySet()) {
            StringJoiner cells = new StringJoiner(", ", sort.getKey() + ": ", "");
            for (var input : inputs.entrySet()) {
                int[] a = input.getValue().clone();
                long[] c = sort.getValue().apply(a);
                for (int i = 1; i < a.length; i++) if (a[i - 1] > a[i]) throw new AssertionError();
                cells.add(input.getKey() + " " + c[0] + "/" + c[1]);
            }
            System.out.println(cells);
        }
    }
}

// selection: sorted 499500/0, shuffled 499500/995, reversed 499500/500
// bubble: sorted 999/0, shuffled 499409/248463, reversed 499500/499500
// bubble, no early exit: sorted 499500/0, shuffled 499500/248463, reversed 499500/499500
// insertion: sorted 999/0, shuffled 249457/248463, reversed 499500/499500
// shell: sorted 8006/0, shuffled 15226/7725, reversed 11716/4700
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

// each returns [comparisons, swaps or shifts]
function selection(a) {
    let comps = 0, moves = 0;
    for (let i = 0; i < a.length - 1; i++) {
        let smallest = i;
        for (let j = i + 1; j < a.length; j++) {
            comps++;
            if (a[j] < a[smallest]) smallest = j;
        }
        if (smallest !== i) {
            [a[i], a[smallest]] = [a[smallest], a[i]];
            moves++;
        }
    }
    return [comps, moves];
}

function bubble(a, early = true) {
    let comps = 0, moves = 0;
    for (let end = a.length - 1; end > 0; end--) {
        let swapped = false;
        for (let j = 0; j < end; j++) {
            comps++;
            if (a[j] > a[j + 1]) {
                [a[j], a[j + 1]] = [a[j + 1], a[j]];
                moves++;
                swapped = true;
            }
        }
        if (early && !swapped) break;
    }
    return [comps, moves];
}

function insertion(a, gap = 1) {          // gap 1 is insertion sort; Shell sort runs it for shrinking gaps
    let comps = 0, moves = 0;
    for (let i = gap; i < a.length; i++) {
        const key = a[i];
        let j = i;
        while (j >= gap) {
            comps++;
            if (a[j - gap] <= key) break;
            a[j] = a[j - gap];
            moves++;
            j -= gap;
        }
        a[j] = key;
    }
    return [comps, moves];
}

function shell(a) {
    let comps = 0, moves = 0;
    for (let gap = Math.floor(a.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
        const [c, m] = insertion(a, gap);
        comps += c;
        moves += m;
    }
    return [comps, moves];
}

const n = 1000;
const inputs = [["sorted", Array.from({ length: n }, (_, i) => i)], ["shuffled", shuffled(n)],
    ["reversed", Array.from({ length: n }, (_, i) => n - 1 - i)]];
const sorts = [["selection", selection], ["bubble", (a) => bubble(a, true)],
    ["bubble, no early exit", (a) => bubble(a, false)], ["insertion", (a) => insertion(a, 1)], ["shell", shell]];
for (const [name, sortIt] of sorts) {
    const cells = inputs.map(([kind, values]) => {
        const a = values.slice();
        const [comps, moves] = sortIt(a);
        if (a.some((v, i) => i > 0 && a[i - 1] > v)) throw new Error("not sorted");
        return `${kind} ${comps}/${moves}`;
    });
    console.log(`${name}: ${cells.join(", ")}`);
}

// selection: sorted 499500/0, shuffled 499500/995, reversed 499500/500
// bubble: sorted 999/0, shuffled 499409/248463, reversed 499500/499500
// bubble, no early exit: sorted 499500/0, shuffled 499500/248463, reversed 499500/499500
// insertion: sorted 999/0, shuffled 249457/248463, reversed 499500/499500
// shell: sorted 8006/0, shuffled 15226/7725, reversed 11716/4700
SortSortedShuffledReversed
Selection499,500 / 0499,500 / 995499,500 / 500
Bubble999 / 0499,409 / 248,463499,500 / 499,500
Bubble, no early exit499,500 / 0499,500 / 248,463499,500 / 499,500
Insertion999 / 0249,457 / 248,463499,500 / 499,500
Shell8,006 / 015,226 / 7,72511,716 / 4,700

Each cell is comparisons / swaps or shifts. Selection sort always makes 499,500 comparisons, whatever the order, but at most 999 swaps: the one to use when a write costs far more than a comparison. Bubble sort and insertion sort move once for every pair of values out of order, 248,463 pairs on this shuffle, and both stop early on sorted input: 999 comparisons, no moves. Insertion sort does that with fewer comparisons than bubble sort on the shuffle, which is why library sorts use it for short or nearly sorted runs (Best, Worst and Average Case times its best, worst and average case).

Shell sort runs insertion sort over values a gap apart, halving the gap each round down to 1, so far-out values travel in long jumps. It moved values 7,725 times on the shuffle against insertion sort's 248,463; with this gap sequence its worst case is still O(n²).

Sort by Hand. Pick a sort and an input, then make each decision the sort makes: swap or keep, shift or place, a new smallest or not. A move the sort wouldn't make is refused, and the counters compare your run with the other two sorts on the same input.

Sort by Hand: make each decision of selection, bubble or insertion sort

Which simple sorts are stable

Back to the class list: a sort used for a second key has to be stable. On three cards, comparing the numbers only, where 2a starts before 2b:

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

using Card = pair<int, char>;                 // a number and a letter; the sorts compare numbers only

void selection(vector<Card>& a) {
    for (int i = 0; i + 1 < (int) a.size(); i++) {
        int smallest = i;
        for (int j = i + 1; j < (int) a.size(); j++)
            if (a[j].first < a[smallest].first) smallest = j;
        swap(a[i], a[smallest]);
    }
}

void bubble(vector<Card>& a) {
    for (int end = a.size() - 1; end > 0; end--)
        for (int j = 0; j < end; j++)
            if (a[j].first > a[j + 1].first) swap(a[j], a[j + 1]);
}

void insertion(vector<Card>& a) {
    for (int i = 1; i < (int) a.size(); i++) {
        Card key = a[i];
        int j = i;
        while (j > 0 && a[j - 1].first > key.first) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = key;
    }
}

int main() {
    vector<pair<string, void (*)(vector<Card>&)>> sorts = {
        {"selection", selection}, {"bubble", bubble}, {"insertion", insertion}};
    for (auto& sort : sorts) {
        vector<Card> cards = {{2, 'a'}, {2, 'b'}, {1, 'c'}};
        sort.second(cards);
        printf("%s:", sort.first.c_str());
        for (auto& card : cards) printf(" %d%c", card.first, card.second);
        printf("\n");
    }
}

// selection: 1c 2b 2a
// bubble: 1c 2a 2b
// insertion: 1c 2a 2b
def selection(a):                     # cards of a number and a letter; the sorts compare numbers only
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j][0] < a[smallest][0]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]


def bubble(a):
    for end in range(len(a) - 1, 0, -1):
        for j in range(end):
            if a[j][0] > a[j + 1][0]:
                a[j], a[j + 1] = a[j + 1], a[j]


def insertion(a):
    for i in range(1, len(a)):
        key, j = a[i], i
        while j > 0 and a[j - 1][0] > key[0]:
            a[j] = a[j - 1]
            j -= 1
        a[j] = key


for sort_it in (selection, bubble, insertion):
    cards = [(2, "a"), (2, "b"), (1, "c")]
    sort_it(cards)
    print(f"{sort_it.__name__}:", " ".join(f"{num}{letter}" for num, letter in cards))

# selection: 1c 2b 2a
# bubble: 1c 2a 2b
# insertion: 1c 2a 2b
import java.util.*;
import java.util.function.*;

public class Main {
    record Card(int num, char letter) {}      // the sorts compare numbers only

    static void selection(Card[] a) {
        for (int i = 0; i + 1 < a.length; i++) {
            int smallest = i;
            for (int j = i + 1; j < a.length; j++)
                if (a[j].num() < a[smallest].num()) smallest = j;
            Card t = a[i]; a[i] = a[smallest]; a[smallest] = t;
        }
    }

    static void bubble(Card[] a) {
        for (int end = a.length - 1; end > 0; end--)
            for (int j = 0; j < end; j++)
                if (a[j].num() > a[j + 1].num()) {
                    Card t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                }
    }

    static void insertion(Card[] a) {
        for (int i = 1; i < a.length; i++) {
            Card key = a[i];
            int j = i;
            while (j > 0 && a[j - 1].num() > key.num()) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = key;
        }
    }

    public static void main(String[] args) {
        Map<String, Consumer<Card[]>> sorts = new LinkedHashMap<>();
        sorts.put("selection", Main::selection);
        sorts.put("bubble", Main::bubble);
        sorts.put("insertion", Main::insertion);
        for (var sort : sorts.entrySet()) {
            Card[] cards = {new Card(2, 'a'), new Card(2, 'b'), new Card(1, 'c')};
            sort.getValue().accept(cards);
            StringBuilder line = new StringBuilder(sort.getKey() + ":");
            for (Card c : cards) line.append(" ").append(c.num()).append(c.letter());
            System.out.println(line);
        }
    }
}

// selection: 1c 2b 2a
// bubble: 1c 2a 2b
// insertion: 1c 2a 2b
function selection(a) {                  // cards of a number and a letter; the sorts compare numbers only
    for (let i = 0; i + 1 < a.length; i++) {
        let smallest = i;
        for (let j = i + 1; j < a.length; j++)
            if (a[j][0] < a[smallest][0]) smallest = j;
        [a[i], a[smallest]] = [a[smallest], a[i]];
    }
}

function bubble(a) {
    for (let end = a.length - 1; end > 0; end--)
        for (let j = 0; j < end; j++)
            if (a[j][0] > a[j + 1][0]) [a[j], a[j + 1]] = [a[j + 1], a[j]];
}

function insertion(a) {
    for (let i = 1; i < a.length; i++) {
        const key = a[i];
        let j = i;
        while (j > 0 && a[j - 1][0] > key[0]) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = key;
    }
}

for (const sortIt of [selection, bubble, insertion]) {
    const cards = [[2, "a"], [2, "b"], [1, "c"]];
    sortIt(cards);
    console.log(`${sortIt.name}: ${cards.map(([num, letter]) => num + letter).join(" ")}`);
}

// selection: 1c 2b 2a
// bubble: 1c 2a 2b
// insertion: 1c 2a 2b

Bubble and insertion sort move a value only past a strictly bigger neighbour, so equal values never pass each other: stable. Selection sort's swap is long. Swapping 1c into place sent 2a to the end, past its equal 2b: not stable.

Two dashed panels for the cards 2a, 2b and 1c, the 2s orange and 1c blue. Left, crossed, selection sort: the row 2a 2b 1c with an orange arrow under it from 1c to the front and a red one over it from 2a to the back; pass 1 swaps 1c with 2a, and 2a jumps past 2b; the row 1c 2b 2a with the 2s ringed in red; pass 2: 2b and 2a are equal, so nothing moves back; 2a ends after 2b: not stable. Right, ticked, insertion sort: the row 2a 2b 1c with an orange arrow under it from 1c to the front and green arrows over it moving 2a and 2b one place right; 2a and 2b each shift one place, and 1c drops in front; the row 1c 2a 2b with the 2s ringed in green; 2a never moved past 2b: only bigger values pass a key; 2a stays before 2b: stable. Focal line: a long swap jumps equals; a shift past bigger values can't. Title: a long swap jumps an equal.

The library sort

In practice you call the library. Every one takes a key or a comparator for your own order (the language primers, Python for DSA through JavaScript for DSA, show the calls), and each promises something different:

LanguageCallStable?
C++sortNo
C++stable_sortYes
JavaArrays.sort on int[]No (equal ints look alike)
JavaList.sort, Arrays.sort on objectsYes
Pythonsorted, list.sortYes
JavaScriptarray.sortYes

Under them are O(n log n) sorts that switch to insertion sort for short runs: introsort in C++'s sort, a dual-pivot quick sort for Java's primitives, and Timsort, a merge sort that finds runs already in order, for Python, Java's objects and JavaScript. Against insertion sort on the same shuffled values:

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

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}

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

double seconds(function<void()> f) {
    auto start = chrono::steady_clock::now();
    f();
    return chrono::duration<double>(chrono::steady_clock::now() - start).count();
}

int main() {
    for (int n : {10000, 100000}) {
        vector<int> a = shuffled(n), b = a;
        double slow = seconds([&] { insertionSort(a); });
        double fast = seconds([&] { sort(b.begin(), b.end()); });
        printf("%d: insertion sort %.3fs, library sort %.4fs\n", n, slow, fast);
    }
}

// 10000: insertion sort 0.016s, library sort 0.0005s
// 100000: insertion sort 1.620s, library sort 0.0070s
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums

import time


def insertion_sort(a):
    for i in range(1, len(a)):
        key, j = a[i], i
        while j > 0 and a[j - 1] > key:
            a[j] = a[j - 1]
            j -= 1
        a[j] = key


def seconds(f, a):
    start = time.perf_counter()
    f(a)
    return time.perf_counter() - start


n = 10000                             # 100,000 would take minutes here
a = shuffled(n)
b = a[:]
slow, fast = seconds(insertion_sort, a), seconds(list.sort, b)
print(f"{n}: insertion sort {slow:.3f}s, library sort {fast:.4f}s")

# 10000: insertion sort 5.019s, library sort 0.0014s
import java.util.*;

public class Main {
    static int seed = (int) 2463534242L;

    static int randomBelow(int bound) {          // xorshift: the same numbers in every language
        seed ^= seed << 13;
        seed ^= seed >>> 17;
        seed ^= seed << 5;
        return Integer.remainderUnsigned(seed, bound);
    }

    static int[] shuffled(int n) {               // 0 .. n-1 in a random order
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = randomBelow(i + 1), t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

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

    public static void main(String[] args) {
        for (int n : new int[]{10000, 100000}) {
            int[] a = shuffled(n), b = a.clone();
            long t0 = System.nanoTime();
            insertionSort(a);
            long t1 = System.nanoTime();
            Arrays.sort(b);
            long t2 = System.nanoTime();
            System.out.printf("%d: insertion sort %.3fs, library sort %.4fs%n", n, (t1 - t0) / 1e9, (t2 - t1) / 1e9);
        }
    }
}

// 10000: insertion sort 0.168s, library sort 0.0133s
// 100000: insertion sort 1.365s, library sort 0.0229s
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

function insertionSort(a) {
    for (let i = 1; i < a.length; i++) {
        const key = a[i];
        let j = i;
        while (j > 0 && a[j - 1] > key) { a[j] = a[j - 1]; j--; }
        a[j] = key;
    }
}

for (const n of [10000, 100000]) {
    const a = shuffled(n), b = a.slice();
    let start = process.hrtime.bigint();
    insertionSort(a);
    const slow = Number(process.hrtime.bigint() - start) / 1e9;
    start = process.hrtime.bigint();
    b.sort((x, y) => x - y);
    const fast = Number(process.hrtime.bigint() - start) / 1e9;
    console.log(`${n}: insertion sort ${slow.toFixed(3)}s, library sort ${fast.toFixed(4)}s`);
}

// 10000: insertion sort 0.076s, library sort 0.0038s
// 100000: insertion sort 7.300s, library sort 0.0389s

At 100,000 values insertion sort took 1.62 s in C++, 1.36 s in Java and 7.30 s in JavaScript, against 7.0 ms, 22.9 ms and 38.9 ms for the library sort; Python's insertion sort took 5.02 s for 10,000, its library sort 1.4 ms. Write the simple sorts to learn them, and when a problem asks for them; otherwise call the library.

Spotting it

The clues for sorting first: the answer depends on order but not on where values started (the closest pair, the kth smallest, duplicates, ranks), things to schedule or merge by time, or "arrange" and "rearrange". Near misses:

  • The k smallest of many values: a heap of size k is O(n log k) (Top K and the Kth Element).
  • Values in a small range: count them instead of comparing (Counting, Bucket and Radix Sort).
  • When the answer needs the original positions, as Two Sum's does: sort (value, index) pairs, or use a hash map (Hashing).

Mistakes that cost an interview

Sorting by a second key with an unstable sort. std::sort scrambled 93 of 195 grade-mates above. Use std::stable_sort, or one comparator that compares the grade, then the name.

A comparator that never says equal. A comparator must call two values equal when neither comes first. Java's sort checks:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Integer[] v = new Integer[1000];
        int s = 12345;
        for (int i = 0; i < v.length; i++) {      // 1,000 values from 0 to 9
            s = s * 1103515245 + 12345;
            v[i] = (s >>> 16) % 10;
        }
        try {
            Arrays.sort(v, (x, y) -> x <= y ? -1 : 1);   // never says "equal"
            System.out.println("sorted");
        } catch (IllegalArgumentException e) {
            System.out.println("threw: " + e.getMessage());
        }
    }
}

// threw: Comparison method violates its general contract!

C++ doesn't check. Its sort needs a < b, and a <= b is undefined behaviour: on 100,000 equal values it took 2.05 s, against 1.0 ms with <, and it may also read past the array.

Bubble sort without the early exit. On sorted input it still made 499,500 comparisons, where the version that stops after a pass with no swap made 999.

Recursion depth in Python. Bubble Sort with Recursion and Insertion Sort with Recursion allow 1,000 values, one call per value:

import sys


def bubble(arr, n):                   # one pass, then the same on the first n - 1
    if n == 1:
        return
    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
    bubble(arr, n - 1)


arr = list(range(1000, 0, -1))
try:
    bubble(arr, len(arr))
except RecursionError as e:
    print("RecursionError:", e)
sys.setrecursionlimit(10_000)         # 1,000 calls deep needs more than Python's default limit of 1,000
bubble(arr, len(arr))
print(arr[:5])

# RecursionError: maximum recursion depth exceeded in comparison
# [1, 2, 3, 4, 5]

Python stops at 1,000 frames by default. Raise the limit, or write the sort as a loop.

JavaScript's sort without a comparator. It compares values as text:

console.log([10, 9, 1, 100].sort().join(" "));                  // no comparator: compared as text
console.log([10, 9, 1, 100].sort((a, b) => a - b).join(" "));

// 1 10 100 9
// 1 9 10 100

Pass (a, b) => a - b for numbers (JavaScript for DSA).

Check yourself

Quiz

1 / 6

Multiple choice

Which of the three simple sorts can change the order of two equal values?

Practice

In this section, easy to hard:

  • Selection Sort, Bubble Sort and Insertion Sort: the three above.
  • Bubble Sort with Recursion: one pass, then recurse on the rest; mind Python's depth limit.
  • Rank Transform of an Array: sort the distinct values, then look each one up.
  • Insertion Sort with Recursion: sort the first n − 1, then insert the last.

Next: Merge Sort and Counting Inversions, the first O(n log n) sort, and what it can count on the way.