Algorithm dossier

  • Category: Sort
  • Worst-case complexity: O(n log n)
  • Approach: Iterative
  • Data structure: Heap
  • First formalised: 1960s

Why this snippet is Heap Sort

Why heapsort. Two phases. Phase one (the first reversed-range loop) builds a max-heap in-place using the sift-down helper s. Phase two repeatedly swaps the root (largest) with the last unsorted slot, shrinks the heap, and re-sifts. Tell. The sift-down's 2 * i + 1 child arithmetic is the signature of an array-backed binary heap — no heap pointer types, just index math.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.