Overview

Before a quant system can search, rank, or join data at scale, it needs a small set of building blocks whose costs are known exactly: a way to store an ordered sequence and grow it cheaply, a way to look values up by key in expected constant time, and a family of sorting algorithms whose $\Theta(n\log n)$ or better costs make every "sort then process" pipeline tractable. This topic builds all of it: arrays, linked lists, stacks, and queues as the linear-structure vocabulary; the doubling strategy and amortized analysis that explain why a growable array is still $O(1)$ per append despite occasional expensive resizes; hash tables for expected-$O(1)$ keyed lookup; heapsort and the heap data structure it introduces (reused immediately as a priority queue); quicksort, whose worst case motivates randomization, reusing Topic 1's indicator-variable machinery directly; linear-time sorting for when comparisons can be avoided; and order statistics (quickselect) for when only a rank, not a full sort, is needed. This is the deepest topic in the unit because it is where a quant reader's daily toolkit — the operations list.append, dict[key], sorted(...), heapq.heappush — gets its cost guarantees derived from first principles rather than taken on faith.