Sorting Algorithms Explained: Merge Sort, Quicksort & More

Sorting is the most common first step in algorithm problems: once the data is in order, duplicates sit together, the closest values are neighbours, and two pointers and binary search become possible. Every language has a sort built in, but interviews ask you to write merge sort or quicksort, their inner ideas — merging, partitioning, counting — solve other problems, and you need to know whether your library's sort is stable and what it costs.

Why sorting comes first

What is the smallest difference between any two numbers in an array? Comparing every pair costs n(n − 1)/2 checks, about five billion for n = 100,000. Sorting first costs about 1.7 million comparisons, and then only the n − 1 neighbouring pairs need checking.

The idea: order puts related values side by side

Why only neighbours? If a ≤ b ≤ c, then c − a = (c − b) + (b − a), which is at least either gap on its own: a pair that skips over a value can never be closer than the neighbours inside it. Sorting is what made that argument available.

1. The smallest difference between two of these 6 numbers could hide in any of the 15 pairs, and checking every pair is O(n²). Sorting first changes that.
2. Sorted, in O(n log n). Now each number's closest partner is right next to it: anything further along is past that neighbour, so it is at least as far away. Only 5 neighbouring pairs are left to check.
3. 4 and 8 are the first neighbours: 8 − 4 = 4, the best so far. The gap is written under the space between them.
4. 8 and 11 differ by 3, smaller than 4, so the best becomes 3.
5. 11 and 19 differ by 8, not below the best 3, which stays. Any pair further apart spans two or more of these gaps, so the smallest gap is the answer.
6. 19 and 27 differ by 8, not below the best 3, which stays.
7. 27 and 33 differ by 6, not below the best 3, which stays.
8. The smallest difference is 3, between 8 and 11. Sorting cost O(n log n) and the scan 5 comparisons, so O(n log n) in all, against 15 checks unsorted.

The same happens again and again: equal values become adjacent, sums become monotone for two pointers and binary search, intervals sorted by start merge in one sweep, and greedy algorithms usually need the data in order first.

The simple sorts: bubble, selection and insertion

These three are O(n²), and each is asked in interviews:

• Bubble sort swaps out-of-order neighbours pass after pass, carrying the largest value to the end; a pass with no swap ends it early. Stable.
• Selection sort swaps the smallest remaining value to the front, n − 1 times: always n(n − 1)/2 comparisons, at most n − 1 swaps. Unstable.
• Insertion sort grows a sorted prefix, shifting larger values right to make a gap.

1. Insertion sort grows a sorted prefix, the way most people sort a hand of cards: take the next element, shift every larger value in the prefix one place right, and drop the element into the gap. One element alone is sorted.
2. Take 2. 5 is larger, so it shifts one place right and 2 drops into the gap: 1 shift, each fixing one pair that was out of order.
3. Take 4. 5 is larger, so it shifts one place right and 4 drops into the gap: 1 shift, each fixing one pair that was out of order.
4. Take 6: it is larger than everything before it, so nothing moves. On already sorted input every step is like this one, and insertion sort runs in O(n).
5. Take 1. 6, 5, 4, 2 are larger, so they shift one place right and 1 drops into the gap: 4 shifts, each fixing one pair that was out of order.
6. Take 3. 6, 5, 4 are larger, so they shift one place right and 3 drops into the gap: 3 shifts, each fixing one pair that was out of order.
7. Sorted with 9 shifts — exactly the 9 inversions, pairs out of order, in the input. So the cost is O(n + inversions): close to O(n) when the data is nearly sorted, O(n²) when it is reversed.

Each shift fixes one inversion, so insertion sort costs O(n + d) for d inversions. That, and its tiny constant factors, is why introsort and TimSort hand short pieces to it.

Merge sort: divide, sort, merge

Merge sort sorts each half recursively and merges the two sorted halves. The merge is two pointers on two arrays: the smallest value not yet placed is at one of the two fronts, so take the smaller front.

1. Merge sort splits the array in half, sorts each half the same way, and merges the two sorted halves into one. A piece of one element is already sorted, which is where the splitting stops.
2. Split until every piece holds one element: 3 levels below the top for 7 values, about log₂ n. Nothing has been compared yet — all the work is in the merges.
3. Merge [38] and [27]: the smaller front, 27, goes first, then 38. A sorted run of two rises one level.
4. Merge [43] and [3]: the smaller front, 3, goes first, then 43. A sorted run of two rises one level.
5. Merge [27 38] and [3 43]: take the smaller of the two fronts each time — 3, 27, 38, 43. Each value is placed once, so merging 4 values costs 4 steps.
6. Merge [9] and [82]: the smaller front, 9, goes first, then 82. A sorted run of two rises one level.
7. Merge [9 82] and [10]: take the smaller of the two fronts each time — 9, 10, 82. Each value is placed once, so merging 3 values costs 3 steps.
8. Merge [3 27 38 43] and [9 10 82]: take the smaller of the two fronts each time — 3, 9, 10, 27, 38, 43, 82. Each value is placed once, so merging 7 values costs 7 steps.
9. Sorted. Each level of merges handles every one of the 7 values once, and there are about log₂ n levels, so merge sort is O(n log n) on every input — at the price of an O(n) buffer for the merges.

It is O(n log n) on every input — about log₂ n levels, each touching every element once — and stable, because on equal fronts the merge takes the left one (<=, not <). Its cost is an O(n) buffer.

The code

The program prints every merge, so you can watch the sorted runs grow.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string join(const vector<int>& a, int from, int to) {    // a[from..to] as "x y z"
    string out;
    for (int i = from; i <= to; i++) out += (i > from ? " " : "") + to_string(a[i]);
    return out;
}

// Merges the sorted runs a[lo..mid] and a[mid+1..hi] into one sorted run.
void merge(vector<int>& a, int lo, int mid, int hi, vector<int>& tmp) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];   // <= takes the left value on a tie: stable
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];        // copy whichever run is left over
    while (j <= hi) tmp[k++] = a[j++];
    cout << "merge [" << join(a, lo, mid) << "] + [" << join(a, mid + 1, hi) << "] -> ["
         << join(tmp, lo, hi) << "]\n";
    for (k = lo; k <= hi; k++) a[k] = tmp[k];
}

// Sorts a[lo..hi], both ends included.
void mergeSort(vector<int>& a, int lo, int hi, vector<int>& tmp) {
    if (lo >= hi) return;                      // one element (or none) is already sorted
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid, tmp);                // sort the left half
    mergeSort(a, mid + 1, hi, tmp);            // sort the right half
    merge(a, lo, mid, hi, tmp);                // combine the two sorted halves
}

int main() {
    vector<int> nums = {38, 27, 43, 3, 9, 82, 10};
    int n = (int)nums.size();
    cout << "before: " << join(nums, 0, n - 1) << "\n";
    vector<int> tmp(n);
    mergeSort(nums, 0, n - 1, tmp);
    cout << "after:  " << join(nums, 0, n - 1) << "\n";
    return 0;
}

public class Main {
    static String join(int[] a, int from, int to) {          // a[from..to] as "x y z"
        StringBuilder out = new StringBuilder();
        for (int i = from; i <= to; i++) out.append(i > from ? " " : "").append(a[i]);
        return out.toString();
    }

    // Merges the sorted runs a[lo..mid] and a[mid+1..hi] into one sorted run.
    static void merge(int[] a, int lo, int mid, int hi, int[] tmp) {
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];   // <= takes the left value on a tie: stable
            else tmp[k++] = a[j++];
        }
        while (i <= mid) tmp[k++] = a[i++];        // copy whichever run is left over
        while (j <= hi) tmp[k++] = a[j++];
        System.out.println("merge [" + join(a, lo, mid) + "] + [" + join(a, mid + 1, hi) + "] -> ["
                + join(tmp, lo, hi) + "]");
        for (k = lo; k <= hi; k++) a[k] = tmp[k];
    }

    // Sorts a[lo..hi], both ends included.
    static void mergeSort(int[] a, int lo, int hi, int[] tmp) {
        if (lo >= hi) return;                      // one element (or none) is already sorted
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid, tmp);                // sort the left half
        mergeSort(a, mid + 1, hi, tmp);            // sort the right half
        merge(a, lo, mid, hi, tmp);                // combine the two sorted halves
    }

    public static void main(String[] args) {
        int[] nums = {38, 27, 43, 3, 9, 82, 10};
        int n = nums.length;
        System.out.println("before: " + join(nums, 0, n - 1));
        mergeSort(nums, 0, n - 1, new int[n]);
        System.out.println("after:  " + join(nums, 0, n - 1));
    }
}

def join(a, lo, hi):
    """a[lo..hi] as "x y z"."""
    return " ".join(str(x) for x in a[lo:hi + 1])


def merge(a, lo, mid, hi, tmp):
    """Merge the sorted runs a[lo..mid] and a[mid+1..hi] into one sorted run."""
    i, j, k = lo, mid + 1, lo
    while i <= mid and j <= hi:
        if a[i] <= a[j]:                       # <= takes the left value on a tie: stable
            tmp[k] = a[i]
            i += 1
        else:
            tmp[k] = a[j]
            j += 1
        k += 1
    tmp[k:hi + 1] = a[i:mid + 1] + a[j:hi + 1]  # copy whichever run is left over
    print(f"merge [{join(a, lo, mid)}] + [{join(a, mid + 1, hi)}] -> [{join(tmp, lo, hi)}]")
    a[lo:hi + 1] = tmp[lo:hi + 1]


def merge_sort(a, lo, hi, tmp):
    """Sort a[lo..hi], both ends included."""
    if lo >= hi:                               # one element (or none) is already sorted
        return
    mid = lo + (hi - lo) // 2
    merge_sort(a, lo, mid, tmp)                # sort the left half
    merge_sort(a, mid + 1, hi, tmp)            # sort the right half
    merge(a, lo, mid, hi, tmp)                 # combine the two sorted halves


nums = [38, 27, 43, 3, 9, 82, 10]
n = len(nums)
print("before:", join(nums, 0, n - 1))
merge_sort(nums, 0, n - 1, [0] * n)
print("after: ", join(nums, 0, n - 1))

// a[from..to] as "x y z"
function join(a, from, to) {
  return a.slice(from, to + 1).join(" ");
}

// Merges the sorted runs a[lo..mid] and a[mid+1..hi] into one sorted run.
function merge(a, lo, mid, hi, tmp) {
  let i = lo;
  let j = mid + 1;
  let k = lo;
  while (i <= mid && j <= hi) {
    if (a[i] <= a[j]) tmp[k++] = a[i++]; // <= takes the left value on a tie: stable
    else tmp[k++] = a[j++];
  }
  while (i <= mid) tmp[k++] = a[i++]; // copy whichever run is left over
  while (j <= hi) tmp[k++] = a[j++];
  console.log(`merge [${join(a, lo, mid)}] + [${join(a, mid + 1, hi)}] -> [${join(tmp, lo, hi)}]`);
  for (k = lo; k <= hi; k++) a[k] = tmp[k];
}

// Sorts a[lo..hi], both ends included.
function mergeSort(a, lo, hi, tmp) {
  if (lo >= hi) return; // one element (or none) is already sorted
  const mid = lo + Math.floor((hi - lo) / 2);
  mergeSort(a, lo, mid, tmp); // sort the left half
  mergeSort(a, mid + 1, hi, tmp); // sort the right half
  merge(a, lo, mid, hi, tmp); // combine the two sorted halves
}

const nums = [38, 27, 43, 3, 9, 82, 10];
const n = nums.length;
console.log(`before: ${join(nums, 0, n - 1)}`);
mergeSort(nums, 0, n - 1, new Array(n));
console.log(`after:  ${join(nums, 0, n - 1)}`);

before: 38 27 43 3 9 82 10
merge [38] + [27] -> [27 38]
merge [43] + [3] -> [3 43]
merge [27 38] + [3 43] -> [3 27 38 43]
merge [9] + [82] -> [9 82]
merge [9 82] + [10] -> [9 10 82]
merge [3 27 38 43] + [9 10 82] -> [3 9 10 27 38 43 82]
after:  3 9 10 27 38 43 82

A value from the right half placed before mid − i + 1 values still waiting on the left was out of order with all of them; summing those counts every inversion in O(n log n): Count Inversions.

Quicksort: partition around a pivot

Quicksort turns merge sort inside out: it partitions around a pivot first, so the pivot lands in its final place, then sorts the two sides — no merge, no buffer. Lomuto's partition is the read-and-write pointer pattern from two pointers.

1. Quicksort first partitions: it picks a pivot — here the middle element, 4 — and rearranges the range so that smaller values come before it and the rest after. No merge is needed afterwards.
2. Park the pivot at the end by swapping it with the last element. store = 0 marks where the next smaller value goes: everything before store will be smaller than 4.
3. a[0] = 7 is not smaller than 4: it stays where it is and only i moves on. The range always reads: smaller than the pivot | not smaller | not yet seen.
4. a[1] = 2 < 4: swap it with a[0] = 7, the first value not smaller, and move store to 1. The front still holds only values below the pivot.
5. a[2] = 9 is not smaller than 4: it stays, and only i moves on.
6. a[3] = 3 < 4: swap it with a[1] = 7, the first value not smaller, and move store to 2. The front still holds only values below the pivot.
7. a[4] = 1 < 4: swap it with a[2] = 9, the first value not smaller, and move store to 3. The front still holds only values below the pivot.
8. a[5] = 8 is not smaller than 4: it stays, and only i moves on.
9. Swap the pivot into a[3]: [2 3 1] 4 [9 8 7]. 4 is now exactly where it belongs in the sorted array, and each side is sorted the same way, recursively.

The pivot decides the speed. Pivots near the middle give about log₂ n levels; a pivot that is always the smallest or largest leaves one side empty and costs about n²/2. The first or last element does exactly that on sorted input, so real quicksorts pick a random element, the middle one or the median of three.

Quicksort is not stable, and many equal values slow Lomuto's partition; a three-way partition, as in Sort Colors, fixes that.

The code

#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

string join(const vector<int>& a, int from, int to) {    // a[from..to] as "x y z"
    string out;
    for (int i = from; i <= to; i++) out += (i > from ? " " : "") + to_string(a[i]);
    return out;
}

// Lomuto partition of a[lo..hi]: returns the pivot's final index.
int partition(vector<int>& a, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    swap(a[mid], a[hi]);                       // pivot: the middle element, parked at the end
    int pivot = a[hi];
    int store = lo;                            // a[lo..store-1] holds values < pivot
    for (int i = lo; i < hi; i++) {
        if (a[i] < pivot) {
            swap(a[i], a[store]);
            store++;
        }
    }
    swap(a[store], a[hi]);                     // the pivot drops into its final place
    return store;
}

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    cout << "pivot " << a[p] << ": [" << join(a, lo, p - 1) << "] " << a[p] << " ["
         << join(a, p + 1, hi) << "]\n";
    quickSort(a, lo, p - 1);                   // sort the smaller values
    quickSort(a, p + 1, hi);                   // sort the larger values
}

int main() {
    vector<int> nums = {7, 2, 9, 4, 1, 8, 3};
    int n = (int)nums.size();
    cout << "before: " << join(nums, 0, n - 1) << "\n";
    quickSort(nums, 0, n - 1);
    cout << "after:  " << join(nums, 0, n - 1) << "\n";
    return 0;
}

public class Main {
    static String join(int[] a, int from, int to) {          // a[from..to] as "x y z"
        StringBuilder out = new StringBuilder();
        for (int i = from; i <= to; i++) out.append(i > from ? " " : "").append(a[i]);
        return out.toString();
    }

    static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    // Lomuto partition of a[lo..hi]: returns the pivot's final index.
    static int partition(int[] a, int lo, int hi) {
        int mid = lo + (hi - lo) / 2;
        swap(a, mid, hi);                          // pivot: the middle element, parked at the end
        int pivot = a[hi];
        int store = lo;                            // a[lo..store-1] holds values < pivot
        for (int i = lo; i < hi; i++) {
            if (a[i] < pivot) {
                swap(a, i, store);
                store++;
            }
        }
        swap(a, store, hi);                        // the pivot drops into its final place
        return store;
    }

    static void quickSort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        System.out.println("pivot " + a[p] + ": [" + join(a, lo, p - 1) + "] " + a[p] + " ["
                + join(a, p + 1, hi) + "]");
        quickSort(a, lo, p - 1);                   // sort the smaller values
        quickSort(a, p + 1, hi);                   // sort the larger values
    }

    public static void main(String[] args) {
        int[] nums = {7, 2, 9, 4, 1, 8, 3};
        int n = nums.length;
        System.out.println("before: " + join(nums, 0, n - 1));
        quickSort(nums, 0, n - 1);
        System.out.println("after:  " + join(nums, 0, n - 1));
    }
}

def join(a, lo, hi):
    """a[lo..hi] as "x y z"."""
    return " ".join(str(x) for x in a[lo:hi + 1])


def partition(a, lo, hi):
    """Lomuto partition of a[lo..hi]: return the pivot's final index."""
    mid = lo + (hi - lo) // 2
    a[mid], a[hi] = a[hi], a[mid]              # pivot: the middle element, parked at the end
    pivot = a[hi]
    store = lo                                 # a[lo..store-1] holds values < pivot
    for i in range(lo, hi):
        if a[i] < pivot:
            a[i], a[store] = a[store], a[i]
            store += 1
    a[store], a[hi] = a[hi], a[store]          # the pivot drops into its final place
    return store


def quick_sort(a, lo, hi):
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    print(f"pivot {a[p]}: [{join(a, lo, p - 1)}] {a[p]} [{join(a, p + 1, hi)}]")
    quick_sort(a, lo, p - 1)                   # sort the smaller values
    quick_sort(a, p + 1, hi)                   # sort the larger values


nums = [7, 2, 9, 4, 1, 8, 3]
n = len(nums)
print("before:", join(nums, 0, n - 1))
quick_sort(nums, 0, n - 1)
print("after: ", join(nums, 0, n - 1))

// a[from..to] as "x y z"
function join(a, from, to) {
  return a.slice(from, to + 1).join(" ");
}

function swap(a, i, j) {
  const t = a[i];
  a[i] = a[j];
  a[j] = t;
}

// Lomuto partition of a[lo..hi]: returns the pivot's final index.
function partition(a, lo, hi) {
  const mid = lo + Math.floor((hi - lo) / 2);
  swap(a, mid, hi); // pivot: the middle element, parked at the end
  const pivot = a[hi];
  let store = lo; // a[lo..store-1] holds values < pivot
  for (let i = lo; i < hi; i++) {
    if (a[i] < pivot) {
      swap(a, i, store);
      store++;
    }
  }
  swap(a, store, hi); // the pivot drops into its final place
  return store;
}

function quickSort(a, lo, hi) {
  if (lo >= hi) return;
  const p = partition(a, lo, hi);
  console.log(`pivot ${a[p]}: [${join(a, lo, p - 1)}] ${a[p]} [${join(a, p + 1, hi)}]`);
  quickSort(a, lo, p - 1); // sort the smaller values
  quickSort(a, p + 1, hi); // sort the larger values
}

const nums = [7, 2, 9, 4, 1, 8, 3];
const n = nums.length;
console.log(`before: ${join(nums, 0, n - 1)}`);
quickSort(nums, 0, n - 1);
console.log(`after:  ${join(nums, 0, n - 1)}`);

before: 7 2 9 4 1 8 3
pivot 4: [2 3 1] 4 [9 8 7]
pivot 3: [2 1] 3 []
pivot 2: [1] 2 []
pivot 8: [7] 8 [9]
after:  1 2 3 4 7 8 9

To find only the k-th largest value, partition and recurse into the one side that holds position k: O(n) on average. That is quickselect, for Kth Largest Element in an Array (a heap is the other answer).

Counting sort: no comparisons at all

When the values are small integers — marks, ages, letters — counting sort counts each value instead of comparing: O(n + k) for keys 0 to k − 1.

1. Counting sort never compares two values. The keys here are small integers, 0 to 4, so they can be used directly as array indices.
2. One pass counts how often each key occurs: 1 × 0, 3 × 1, 1 × 2, 2 × 3, 1 × 4. That is O(n) work into an array of k = 5 counters.
3. A running total of the counts gives the slot where each key's first copy goes: key v starts after every smaller key. These are prefix sums, [0, 1, 4, 5, 7].
4. Walk the input left to right and put each value at its key's next free slot. The three 1s (#1, #3, #6) land in their input order, so this version is stable — what radix sort needs. O(n + k) in all.

Being stable is what lets radix sort sort digit by digit. Height Checker and Relative Sort Array are counting sorts in disguise; with keys up to 10⁹, use a comparison sort.

Stability and sorting by several keys

A sort is stable if equal elements keep their input order — invisible for numbers, essential for records. To list students by score and alphabetically within a score, write one comparator that breaks ties, or sort twice: by name, then stably by score.

1. A stable sort by score, highest first. The three students on 82 come out as Ravi, Meena, Anil — their input order — and their lines never cross. An unstable sort may cross them.
2. To list equal scores alphabetically with two sorts, sort by the secondary key first: by name. The 82s are now Anil, Meena, Ravi.
3. Then sort stably by score, the main key. Within each score the name order survives, because a stable sort never reorders equals: Anil, Meena, Ravi. Spreadsheets sort by several columns this way.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Student {
    string name;
    int score;
};

string show(const vector<Student>& list) {
    string out;
    for (size_t i = 0; i < list.size(); i++)
        out += (i > 0 ? ", " : "") + list[i].name + " " + to_string(list[i].score);
    return out;
}

int main() {
    vector<Student> students = {{"Ravi", 82}, {"Asha", 91}, {"Meena", 82},
                                {"Kiran", 75}, {"Dev", 91}, {"Anil", 82}};
    auto byScoreDesc = [](const Student& a, const Student& b) { return a.score > b.score; };
    auto byName = [](const Student& a, const Student& b) { return a.name < b.name; };

    vector<Student> scoreOnly = students;
    stable_sort(scoreOnly.begin(), scoreOnly.end(), byScoreDesc);   // ties keep input order
    cout << "score only, stable: " << show(scoreOnly) << "\n";

    vector<Student> one = students;
    sort(one.begin(), one.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) return a.score > b.score;           // main key: score, high first
        return a.name < b.name;                                      // tie: name, A to Z
    });
    cout << "one comparator:     " << show(one) << "\n";

    vector<Student> two = students;
    stable_sort(two.begin(), two.end(), byName);         // secondary key first ...
    stable_sort(two.begin(), two.end(), byScoreDesc);    // ... then stably by the main key
    cout << "two stable sorts:   " << show(two) << "\n";
    return 0;
}

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    static class Student {
        final String name;
        final int score;

        Student(String name, int score) {
            this.name = name;
            this.score = score;
        }
    }

    static String show(Student[] list) {
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < list.length; i++)
            out.append(i > 0 ? ", " : "").append(list[i].name).append(" ").append(list[i].score);
        return out.toString();
    }

    public static void main(String[] args) {
        Student[] students = {new Student("Ravi", 82), new Student("Asha", 91), new Student("Meena", 82),
                              new Student("Kiran", 75), new Student("Dev", 91), new Student("Anil", 82)};
        Comparator<Student> byScoreDesc = (a, b) -> Integer.compare(b.score, a.score);
        Comparator<Student> byName = (a, b) -> a.name.compareTo(b.name);

        Student[] scoreOnly = students.clone();
        Arrays.sort(scoreOnly, byScoreDesc);              // objects use TimSort: stable
        System.out.println("score only, stable: " + show(scoreOnly));

        Student[] one = students.clone();
        Arrays.sort(one, byScoreDesc.thenComparing(byName));   // main key, then name on a tie
        System.out.println("one comparator:     " + show(one));

        Student[] two = students.clone();
        Arrays.sort(two, byName);                         // secondary key first ...
        Arrays.sort(two, byScoreDesc);                    // ... then stably by the main key
        System.out.println("two stable sorts:   " + show(two));
    }
}

students = [("Ravi", 82), ("Asha", 91), ("Meena", 82),
            ("Kiran", 75), ("Dev", 91), ("Anil", 82)]


def show(rows):
    return ", ".join(f"{name} {score}" for name, score in rows)


score_only = sorted(students, key=lambda s: -s[1])      # sorted() is stable: ties keep input order
print(f"score only, stable: {show(score_only)}")

one = sorted(students, key=lambda s: (-s[1], s[0]))     # main key, then name on a tie
print(f"one comparator:     {show(one)}")

two = sorted(students, key=lambda s: s[0])              # secondary key first ...
two = sorted(two, key=lambda s: -s[1])                  # ... then stably by the main key
print(f"two stable sorts:   {show(two)}")

const students = [
  { name: "Ravi", score: 82 }, { name: "Asha", score: 91 }, { name: "Meena", score: 82 },
  { name: "Kiran", score: 75 }, { name: "Dev", score: 91 }, { name: "Anil", score: 82 },
];
const byScoreDesc = (a, b) => b.score - a.score;
const byName = (a, b) => (a.name < b.name ? -1 : a.name > b.name ? 1 : 0);
const show = (list) => list.map((s) => `${s.name} ${s.score}`).join(", ");

const scoreOnly = students.slice().sort(byScoreDesc); // stable since ES2019: ties keep input order
console.log(`score only, stable: ${show(scoreOnly)}`);

const one = students.slice().sort((a, b) => byScoreDesc(a, b) || byName(a, b)); // main key, then name
console.log(`one comparator:     ${show(one)}`);

const two = students.slice().sort(byName).sort(byScoreDesc); // secondary key first, then the main key
console.log(`two stable sorts:   ${show(two)}`);

score only, stable: Asha 91, Dev 91, Ravi 82, Meena 82, Anil 82, Kiran 75
one comparator:     Asha 91, Dev 91, Anil 82, Meena 82, Ravi 82, Kiran 75
two stable sorts:   Asha 91, Dev 91, Anil 82, Meena 82, Ravi 82, Kiran 75

A comparator returns a negative number when the first argument comes first, positive when the second does, zero for a tie; C++ wants a strict "less than" instead. Prefer Integer.compare(b, a) to b - a, which can overflow. Largest Number compares two numbers by which concatenation is bigger.

What your language's sort actually does

TimSort merges runs that are already sorted, so sorted input costs O(n). Introsort is quicksort that falls back to heap sort when recursion gets too deep, and to insertion sort for small pieces. One JavaScript trap: [10, 9, 1, 100].sort() compares strings and gives [1, 10, 100, 9]; pass (a, b) => a - b.

Why no comparison sort beats n log n

Every sort here except counting sort learns about the data only by comparing two elements.

log₂(n!) is about n log₂ n − 1.44 n, so merge sort and heap sort are as good as comparing gets; counting sort escapes only by using values as indices.

Time and space complexity

Quicksort's average is O(n log n). In practice, use the library sort, and count instead of comparing when the keys are small integers.

How to recognise a sorting problem

• The answer depends on order, not original positions: the closest pair, the largest perimeter, the k-th largest.
• You want to pair things up — smallest with smallest, largest with smallest.
• A greedy rule keeps needing "the next smallest" or "the earliest finishing" item.
• The values are small integers in a known range: count instead of compare.

Common mistakes

• Sorting numbers in JavaScript without a comparator, so 100 lands before 9.
• Overflowing comparators: a - b near the integer limits returns the wrong sign.
• Relying on stability you do not have: std::sort and Java's primitive sort are not stable.
• The first element as quicksort's pivot, which makes sorted input O(n²).
• Losing the original indices: sort (value, index) pairs instead of values.

Practice in this order

1. Height Checker: sort and compare — or count, since heights are small.
2. Relative Sort Array: a custom order, neatly a counting sort.
3. Sort Array by Increasing Frequency: two keys, one ascending and one descending.
4. Largest Perimeter Triangle: sort, then a greedy check on neighbours.
5. Sort Colors: three-way partitioning in one pass.
6. Sort an Array: write merge sort or quicksort yourself.
7. Kth Largest Element in an Array: quickselect.
8. Largest Number: a comparator on concatenations.
9. Count Inversions: merge sort that counts while it merges.

The sorting problem list has every problem in the catalogue that leans on sorting. Most greedy solutions begin with a sort, which is the next lesson of this stage: greedy algorithms.