Sorting in DSA: Stability, In-Place & Comparison Sorts

Sorting is the act of rearranging a collection so its elements follow a defined order — usually ascending or descending by some key. It is one of the most studied problems in computer science because sorted data unlocks faster searching, deduplication, grouping, and dozens of other patterns. This page explains the vocabulary every sorting discussion uses — stability, in-place, and comparison vs non-comparison — so the rest of this section makes sense.

This course shows every algorithm in four languages at once. Use the language switcher to read each example in C++, Java, JavaScript, or Python.

What “sorted” means

A collection is sorted when, for every pair of adjacent elements, the first is not “greater” than the second under your ordering rule. That rule is a comparator — a function that, given two elements, says which should come first. For numbers it is usually a < b; for strings it might be alphabetical; for objects it could be “by age, then by name.”

Here is the smallest possible example — sort three numbers ascending using the language’s built-in sort:

#include <algorithm>
#include <vector>

std::vector<int> demo() {
    std::vector<int> a = {3, 1, 2};
    std::sort(a.begin(), a.end()); // {1, 2, 3}
    return a;
}

import java.util.Arrays;

int[] demo() {
    int[] a = {3, 1, 2};
    Arrays.sort(a); // {1, 2, 3}
    return a;
}

function demo() {
  const a = [3, 1, 2];
  a.sort((x, y) => x - y); // [1, 2, 3] — see the comparator note below
  return a;
}

def demo():
    a = [3, 1, 2]
    a.sort()  # [1, 2, 3]
    return a

Gotcha: JavaScript’s default sort() converts elements to strings and sorts them lexicographically, so [10, 2, 1].sort() gives [1, 10, 2]. Always pass a comparator like (x, y) => x - y for numbers. The built-in sorting page covers this in depth.

Stability

A sort is stable if equal elements keep their original relative order. Imagine sorting people by age — if Ann and Bob are both 30 and Ann came first in the input, a stable sort guarantees Ann still comes before Bob afterward.

Why care? Stability lets you sort by multiple keys in passes: sort by name, then stably by age, and you get “by age, ties broken by name” for free. Merge sort, insertion sort, and counting sort are stable; plain quick sort, selection sort, and heap sort are not.

In-place

An algorithm is in-place if it rearranges the data using only a constant (O(1)) or logarithmic amount of extra memory, rather than allocating a second full-sized array. Bubble, selection, insertion, heap, and quick sort are in-place; classic merge sort is not (it needs an O(n) helper buffer).

For beginners: “In-place” is about extra memory — every sort obviously uses the array it is sorting. The question is whether it needs a second big array on the side.

Comparison vs non-comparison sorts

A comparison sort orders elements only by asking “is a before b?” — it never looks inside the values. Every comparison sort has a proven lower bound of O(n log n) comparisons in the worst case; you cannot beat that by being clever, only by changing the rules.

A non-comparison sort exploits structure in the keys themselves — for example, that they are small integers — to sort in O(n) or O(n + k) time without comparing pairs. Counting sort and radix sort are the famous examples. They are faster but only apply to specific kinds of data.

How to read this section

Each following page takes one algorithm and: explains the idea in plain English, shows a correct four-language implementation, and states its best/average/worst time, its space, and whether it is stable. We start with the simple O(n²) sorts (great for learning), move to the O(n log n) workhorses, then cover the linear-time special cases.

Going deeper: In practice you will almost never hand-write a sort — you will call the built-in sort. The value of this section is understanding what those built-ins do, why they pick the algorithm they pick, and when to reach for a specialized sort.

Next: Bubble Sort — the simplest sort to understand. When you finish the section, test yourself with the sorting exercises.