For general comparison-based sorting, O(n log n) is the fundamental target. Algorithms such as Quicksort, Merge Sort, Heap Sort and Timsort operate around this bound, each with different trade-offs. But if we know something special about the input, we can sometimes do better

Pre-order: The manager gives instructions before the employees work. In-order: The manager talks after the left employee finishes but before the right employee starts. Post-order: The manager waits until both employees finish before making a decision.

In this post, I’ll walk through some of the most fundamental data structures I’ve been learning: static arrays, dynamic arrays, stacks, hash maps, and prefix sums.