Master Data Structures & Algorithms

FIFO stands for "First In, First Out." The first item added is the first one removed.

Where you've already used this: Every time you send a document to a printer, it joins a queue. If someone else sent a document before you, theirs prints first. Your document waits its turn and prints when it reaches the front of the line. This is a queue: items are added at the back and removed from the front, in the exact order they arrived. The person (or document, or task) that has been waiting the longest is always served next.

What makes a queue a queue: A queue enforces fairness through its access rule: new items join at the rear, and items leave from the front. This is the opposite of a stack, where everything happens at the same end. In a queue, the item you added first will be the first one removed (FIFO). You cannot skip ahead, and you cannot reach into the middle. This constraint is exactly what you want when order of arrival matters.

The four core operations:

• Enqueue(item): Add a new item to the rear of the queue. The queue grows by one.
• Dequeue(): Remove and return the item at the front. The queue shrinks by one. If the queue is empty, this fails, so always check first.
• Front(): Look at the front item without removing it. Like checking who's next in line without actually serving them.
• Is_Empty(): Returns True if the queue has zero items.

A real Python gotcha with performance: The implementation below stores items in a plain Python list. Adding to the rear with list.append() is O(1), so enqueue() is fast. But removing from the front with list.pop(0) is O(n), because Python has to shift every remaining item down one position to fill the gap at index 0. For a queue with 1,000 items, that means moving 999 items just to remove one. This is fine for learning and for small queues, but real-world Python code uses collections.deque instead. A deque (double-ended queue) is designed to add and remove from both ends in O(1) time, making it the proper choice for production queues.

Where queues appear in computing: Queues are everywhere in systems that need to handle requests fairly and in order. When you press Ctrl+P, your print job enters a queue behind any jobs that were submitted earlier. Customer support ticketing systems use queues so that the person who contacted support first gets helped first. Web servers use request queues to handle incoming traffic: if 1,000 users hit the server at the same time, the requests are queued and processed in order. Operating systems use queues for CPU task scheduling, deciding which program gets processor time next. Message brokers like RabbitMQ and Amazon SQS are essentially sophisticated queue systems that let different parts of a large application communicate reliably.

How it compares to a Stack: Both stacks and queues are containers with restricted access, and both support add/remove operations. The difference is entirely about ordering. A stack gives you the most recent item (LIFO), which is useful for undo operations, backtracking, and recursion tracking. A queue gives you the oldest item (FIFO), which is useful when fairness or arrival order matters. If you're building an undo button, you want a stack. If you're building a task scheduler, you want a queue.

Common mistakes to watch for: (1) Using list.pop(0) in performance-sensitive code. For small queues this is fine, but for queues that grow to thousands of items, the O(n) cost of shifting elements adds up quickly. Switch to collections.deque and use popleft() instead. (2) Confusing a queue with a stack. If you find yourself processing the newest item first, you're using LIFO behaviour and should use a stack instead. (3) Forgetting to check is_empty() before calling dequeue(). Attempting to remove from an empty queue raises an IndexError.

flowchart TD
    Start([Start]) --> Enq["Enqueue: Add item to the rear"]
    Enq --> B{"What do you
want to do?"}
    B -->|Dequeue| C["Remove and return
the front item"]
    B -->|Front| D["Look at the front item
without removing it"]
    B -->|Is Empty| E["Check if the queue
has any items"]
    C --> B
    D --> B
    E --> B
    B -->|Done| Stop([Stop])
                        

You will need this picture for BFS next: closest people finish first because they waited in a fair line.

Dynamic means the structure can grow and shrink as needed with no fixed size limit. Node-based means each item stores its own value and a pointer to the next item in the chain.

Where you've already seen this: Think about a treasure hunt where each clue has two things written on it: a riddle (the data) and directions to the next clue's location (the pointer). You start at clue #1 (the head), solve it, follow the directions to clue #2, solve that, follow the directions to clue #3, and so on. The last clue's directions say "there is no next clue" (that's None in Python). If the organiser wants to add a new clue between clues #2 and #3, they don't have to renumber anything. They just change clue #2's directions to point to the new clue, and the new clue's directions point to #3. That's a linked list.

How it's different from a Python list (array): A Python list stores items in a continuous block of memory, like seats in a cinema row. Item 0 is at seat 0, item 1 is at seat 1, and so on. This means you can instantly access any item by its position (my_list[5] goes directly to seat 5), but inserting or deleting in the middle requires shifting everyone to fill the gap or make room. A linked list stores each item in its own separate location in memory, connected only by pointers. You can't jump directly to item 5 because you don't know where it is. You have to start at the head and follow 5 pointers to get there. But inserting or deleting just requires changing a couple of pointers, with no shifting at all.

The building block, the Node: Every linked list is made of nodes. A node is a small object that holds two things: the data (whatever value you want to store) and a reference to the next node. In Python, this is a simple class with self.data and self.next. The linked list itself only keeps track of one thing: the head node (the very first node in the chain). From the head, you can reach every other node by following the .next pointers.

The core operations and their costs:

• Insert at head, O(1): Create a new node, point its next to the current head, then update the head to the new node. This takes the same amount of time regardless of list size because you don't need to touch any other nodes.
• Insert at tail, O(n): You have to walk the entire chain from head to the last node, then set the last node's next to the new node. For a list with 1,000 nodes, that means following 1,000 pointers.
• Delete by value, O(n): Walk through the list until you find the node with the target value, then make the previous node's next pointer skip over it. The deleted node is now "unlinked" from the chain.
• Search, O(n): Start at the head and follow pointers until you find the value or reach None. There's no way to jump ahead because you don't know where any particular node lives in memory.

When linked lists outperform arrays: Linked lists shine in situations where you frequently insert or delete items at the beginning or middle of the list. In a Python list (array), inserting at the front requires shifting every single element one position to the right, which is O(n). In a linked list, inserting at the head is O(1). This makes linked lists a good choice for implementing stacks (push/pop at the head), for building undo histories where you prepend new actions, and for any scenario where the list size changes rapidly and unpredictably.

When arrays outperform linked lists: If you need to access items by position frequently (my_list[42]), arrays are the clear winner. Arrays give you O(1) random access; linked lists give you O(n). Linked lists also use more memory per item because each node stores a pointer in addition to the data itself. For most everyday Python programming, the built-in list (which is an array underneath) is the right choice. Linked lists become important when you study more advanced data structures like hash tables (which use linked lists to handle collisions) and graphs (where adjacency lists are essentially linked lists).

Common mistakes to watch for: (1) Losing the rest of the list when inserting. If you set head = new_node before setting new_node.next = head, you lose the reference to the old head and everything after it is gone. Always set the new node's pointer first, then update the head. (2) Forgetting to handle the empty list case. If head is None, operations like traversal or deletion need to handle that gracefully rather than trying to access None.next, which crashes with an AttributeError. (3) Not updating the previous node's pointer when deleting. You need to keep track of the node before the one you want to delete, so you can reroute its next pointer around the deleted node.

flowchart LR
    Head([Head]) --> N1["Node: 10"]
    N1 --> N2["Node: 20"]
    N2 --> N3["Node: 30"]
    N3 --> Null([None / End])
                        

The picture is a teaching sketch. The boxes on the right are not real RAM pointers. The Python below really does use next.

Why not always a Python list? Inserting at the front of a Python list shoves every other item over. A linked list just points a new box at the old first box.

Where you've already seen this: Think of a row of labeled lockers in a hallway. You do not walk every locker to find yours — you read the label on your key, the hash function tells you which locker row to open, and you grab the value inside. If two students accidentally get the same locker number, the locker holds a chain of name tags (a tiny linked list). That is a hash map: fast lookup by key, with chains for collisions.

Walk through it: Seven buckets (indices 0–6). Hash = sum of character codes mod 7.

Speed: Average lookup is O(1) — jump to the bucket, maybe walk a short chain. Worst case is O(n) if every key collides in one bucket (then you are back to scanning a list). Python's dict is a hash map under the hood; you met it in the Pre-requisites optional snippet.

flowchart LR
    Key["Key + Value"] --> Hash["hash(key) % buckets"]
    Hash --> Bucket["Bucket index"]
    Bucket --> Chain["Chain in bucket"]
    Chain --> Found["Match key → return value"]
                        

Why after linked lists? Each bucket's chain is a miniature linked list. BFS and Queue lessons used dict for “visited” — same idea, faster than scanning every name in a flat list.

Sorted means the items are arranged from smallest to largest, like 2, 5, 9, 14, 22. If the list isn't sorted, Binary Search cannot work because there is no way to know which half to discard.

Where you've already done this: Think about looking up a word in a physical dictionary. You don't start at page 1 and read forward. You open to roughly the middle, check whether your word comes before or after what you see, and then throw away the half that can't contain it. You keep halving the remaining pages until you land on your word. That's Binary Search. It works by repeatedly splitting the search area in half, checking the middle item, and discarding the half where the target cannot possibly be.

The one strict rule: Binary Search only works on sorted data. If the list isn't in order, there's no way to know whether the target is in the left half or the right half. This is the trade-off: you need sorted data upfront, but in exchange, you get a search that's dramatically faster than checking every item.

Walk through it with real numbers: Say you have the sorted list [3, 7, 11, 15, 19, 23, 27] and you're searching for 19.

Out of 7 items, it took only 3 checks. A linear search on the same list would have taken 5 checks. The difference becomes massive at scale: a sorted list of 1,000,000 items takes Linear Search up to 1,000,000 checks but Binary Search at most 20.

Why "logarithmic" (O(log n)): Each step cuts the remaining data in half. If you start with n items, after one step you have n/2. After two steps, n/4. After three steps, n/8. The number of steps needed to reach 1 remaining item is log₂(n). For 1,000 items that's about 10 steps. For 1,000,000 items it's about 20. This is why Binary Search feels almost instant even on very large datasets, as long as the data is sorted.

How it compares to Linear Search: Linear Search is simpler and works on unsorted data, but it checks every item one by one. Binary Search is restricted to sorted data, but it eliminates half the candidates per step. The key question is: "Will I search this data more than once?" If yes, sorting it once and then using Binary Search for every lookup is almost always worth it. If you only need to search once, sorting first (which itself costs O(n log n)) plus searching (O(log n)) may cost more total work than a single Linear Search (O(n)).

Where you'll actually see it used: Binary Search is everywhere in real software, often hidden inside other tools. Database indexes use it to find records quickly. When you type a word in a search bar and it auto-completes, the app is often doing a binary search over a sorted word list. Python's bisect module is a built-in binary search implementation. Version control systems like Git use binary search (the git bisect command) to pinpoint which specific commit introduced a bug, halving the suspect range with each test.

Common mistakes to watch for: (1) Applying Binary Search to an unsorted list. It will run without crashing, but it will return incorrect results because it discards halves based on ordering that doesn't exist. (2) Getting the midpoint calculation wrong. The formula mid = (low + high) // 2 works in Python, but in languages with fixed-size integers (like C or Java), low + high can overflow. The safer formula is mid = low + (high - low) // 2. (3) Off-by-one errors when updating low and high. After checking the middle, you must set low = mid + 1 or high = mid - 1 (not low = mid or high = mid), otherwise the search can loop forever.

flowchart TD
    Start([Start]) --> A["Your list must be
sorted from low to high"]
    A --> B["Mark the start and
end of your search area"]
    B --> C{"Is there still an
area to search in?"}
    C -- No --> NotFound[("Not found.
Return -1")]
    C -- Yes --> D["Pick the middle item
in your search area"]
    D --> E{"Is this the item?"}
    E -- Yes --> Found[("Found it!
Return its position")]
    E -- No --> F{"Is the middle item
smaller than your target?"}
    F -- Yes --> G["Target is on the right.
Ignore the left half"]
    F -- No --> H["Target is on the left.
Ignore the right half"]
    G --> C
    H --> C
    Found --> Stop([Stop])
    NotFound --> Stop([Stop])
                        

What if the list is not sorted? Binary Search will still run, and it can lie. Example: [9, 1, 4] looking for 1. The middle is 1 — lucky — but looking for 9 it may throw 9 away because it thinks “left is smaller.” Use Linear Search instead.

The // mark: 5 // 2 is 2, not 2.5. We need a whole position number.

Breadth-First Search (BFS) does not scan a sorted list. It walks a graph: it always finishes the close neighbors before it walks farther away.

Where you've already done this: You drop a pebble in a still pond. The first ripple hits the ducks one meter away. The next ripple hits two meters, then three. BFS is that ripple. It never “jumps” to a far node until every closer node has had a turn. A line at a coffee shop is the same idea: whoever has been waiting longest (arrived first) is served first. That line is a Queue — you will meet it properly in Part 3.

A little history: People have asked “what is the shortest walk through a maze?” for a long time. In 1959, Edward F. Moore published a clean method for the shortest path in a maze that is exactly this ripple idea. Social networks still use the same picture: your “friends” are one hop away, “friends of friends” are two hops — that is BFS counting degrees of separation.

On a tree: A tree is a graph with no loops — like an org chart or a folder tree. Start at the boss (the root). BFS visits every person who reports directly to the boss (level 1), then their reports (level 2), and so on. Programmers call this level-order traversal.

Walk through a tiny org chart: Root A has children B and C. B has D and E. Goal: find E.

Notice E is found only after everyone closer to A has been checked. That is the whole algorithm.

On a grid: Treat the floor as graph paper. Each empty square is a node. Its neighbors are up, down, left, right — not diagonals (that keeps later A* math honest). Walls are squares you may not enter. Start in one cell; the goal is another. The ripple fills every cell 1 step away, then 2 steps, then 3. The first time you touch the goal, you have the fewest steps possible, because every cheaper cell was already processed.

Walk through a 3×3 hallway: Start at (0,0), goal at (0,2), wall in the middle of the bottom row.

How it actually works (the loop):

1. Put the start in a queue (FIFO). Remember a parent for every cell so you can walk backward later.
2. Mark start as visited so you never enqueue it twice. Forgetting this on a graph with cycles makes an infinite loop.
3. While the queue is not empty: take the front item. If it is the goal, stop.
4. Look at each neighbor. Skip walls. Skip already visited. Otherwise mark visited, set parent, enqueue.
5. If the queue empties, there is no path.
6. Build the path by following parent pointers from the goal back to the start, then reverse the list.

A stack (last in, first out) would dive down one corridor (depth-first) and can take a long detour. The queue forces “closer first.”

How fast / how much memory: Let V be nodes and E be edges (on a grid, both are about rows × cols). You look at each node and each edge a constant number of times, so time is O(V+E). The queue and visited set can hold every node, so extra memory is O(V). Best case you find the goal next door (tiny). Worst case you paint the whole reachable map.

Where you'll see it in code: Python's collections.deque is the usual queue (do not list.pop(0) — that is slow). Web crawlers keep a frontier of URLs. “Friend of a friend” is unweighted hops. Games flood-fill a fog map. Compilers and browsers walk trees; document.querySelector is “find a node in this tree.” GPS uses BFS-like ideas when every road is treated as the same cost. Connected-component labeling in images is BFS/DFS on pixels.

How it compares: Linear and Binary Search look up a value in a list. BFS looks up a path in a graph. Binary Search needs sorted numbers; BFS needs a neighborhood. Versus A*: BFS is the fair “check every equally close cell.” A* cheats (in a good way) with a guess toward the goal, so it usually paints fewer cells.

Common mistakes: (1) No visited set — cycles replay forever. (2) Using a Python list as a queue with pop(0) — O(n) every pop; use deque. (3) Diagonal moves while later using Manhattan distance in A*. (4) Thinking BFS minimizes kilometers — it minimizes hops when every edge costs 1.

flowchart TD
    Start([Start]) --> Q["Put start in a queue
Mark it visited"]
    Q --> Loop{"Is the queue empty?"}
    Loop -- Yes --> None[("No path.
Stop")]
    Loop -- No --> Pop["Take the front item"]
    Pop --> Goal{"Is this the goal?"}
    Goal -- Yes --> Path["Walk parent pointers
back to start"]
    Path --> Done([Return the path])
    Goal -- No --> Nbr["For each neighbor:
skip walls and visited"]
    Nbr --> Enq["Set parent, mark visited,
enqueue"]
    Enq --> Loop
    None --> Stop([Stop])
    Done --> Stop
                        

List search vs path search: Linear/Binary answer “is this number in the list?” BFS answers “how do I walk from here to there, one handshake at a time?”

A* (say “A star”) still walks a graph, but it does not treat every direction as equal. It keeps a running cost from the start (g) and a heuristic guess of leftover work (h). It always expands the node with the smallest f = g + h.

Where you've already done this: You are in a new city, walking to a cafe you can see on the map. You do not flood every alley equally (BFS). You prefer streets that still point toward the cafe, but you will detour around a closed block. That “how far do I still think it is?” is h. GPS and game characters do the same thing with better maps.

A little history: In 1968 at SRI, Peter Hart, Nils Nilsson, and Bertram Raphael described a family of “A” algorithms. A* was the sweet spot: with an admissible heuristic (a guess that never overestimates), it finds an optimal path and does not waste work the way a blinder search does. Game AI and robot motion planning still teach A* first.

On a tree: Same org chart, but each node also stores a guess “how many hops might remain?” A* does not wait to finish an entire level. It pops the open node whose g + h is smallest — often a child that already looks closer to the goal, even if some cousins are older in the queue sense.

Walk through: Start A (g=0). Children B and C. Goal is under C. If h(C) is smaller than h(B), A* expands C before it finishes B's whole subtree. A step table of the open set (a min-heap in code) is the right picture — not a FIFO line.

Important: stop when the goal is popped from the open set, not merely when you first see it as a neighbor. That is how you know no cheaper f is still hiding.

On a grid: g is steps from start (each move costs 1). h is Manhattan distance: |row_goal - row| + |col_goal - col| — the taxi-meter if there were no walls. With only 4-way moves, you can never beat that number, so h never overestimates. Walls only make the real path longer, never shorter than Manhattan. That is why this guess is admissible.

How it actually works (the loop):

1. Keep an open set as a min-heap of (f, node). Put start in with g=0.
2. Keep g scores and parents. Optionally a closed set of finished nodes.
3. Pop the smallest f. If it is the goal, reconstruct and stop.
4. For each neighbor: skip walls. Compute g2 = g + 1. If this is cheaper than any old g, update parent, f2 = g2 + h(neighbor), push on the heap.
5. If the heap empties, no path.

If you set h = 0 everywhere, A* has no opinion about the goal and, on equal-cost edges, behaves like Dijkstra — which on a grid of cost-1 moves is the same family as BFS. The heuristic is the only extra brain.

How fast / how much memory: Each heap operation is O(log V), and you may touch every edge, so typical time is O(E log V). A perfect heuristic that guessed the true remaining cost would walk almost a straight path. A useless heuristic (h=0) explores like BFS/Dijkstra. Memory is still O(V) for open/closed maps.

Where you'll see it in code: Python heapq (heappush / heappop). Game NPCs walking around crates. Map apps when they have a straight-line (or Manhattan) estimate. Warehouse robots. The 8-puzzle with Manhattan tile distance. Minecraft-style pathfinding. Any time you can guess remaining cost without lying high.

How it compares: BFS paints an expanding disk. A* paints a blob aimed at the goal — usually fewer cells, same optimal hop-count if h is admissible. Linear/Binary still do not apply: you are not probing a sorted array.

Common mistakes: (1) h that overestimates (e.g. “I swear it is 3 steps” when 5 are required) — you can miss the best path. (2) Diagonal steps plus Manhattan (the guess no longer matches the moves). (3) Scanning the whole open list instead of a heap on large maps. (4) Mixing up “visited fewer cells” with “a different destination.”

flowchart TD
    Start([Start]) --> Open["Put start in a min-heap
keyed by f = g + h"]
    Open --> Empty{"Heap empty?"}
    Empty -- Yes --> None[("No path")]
    Empty -- No --> Pop["Pop smallest f"]
    Pop --> IsGoal{"Goal popped?"}
    IsGoal -- Yes --> Path["Follow parents
back to start"]
    Path --> Done([Return the path])
    IsGoal -- No --> Nbr["Each neighbor:
g2 = g + 1"]
    Nbr --> Better{"Cheaper g?"}
    Better -- Yes --> Push["Update parent
push f2 = g2 + h"]
    Better -- No --> Empty
    Push --> Empty
    None --> Stop([Stop])
    Done --> Stop
                        

On a tiny 3-cell walk: start g=0, h=2, f=2. One step toward the goal: g=1, h=1, f=2. Goal: g=2, h=0, f=2. We stop when the goal is taken out of the waiting list, not when we first peek at it.

Admissible means the guess never brags that you are closer than you really are. Footnote: if every guess is 0, A* has no opinion — like BFS on equal steps. That is not a new lesson.

Where you've already done this: Think about the last time you arranged a messy hand of playing cards. You probably didn't scan the whole hand to find the smallest card first. You just looked at two cards next to each other, swapped them if they were out of order, and moved on to the next pair. That's Bubble Sort. It only ever compares neighbours (two items standing right next to each other in the list) and swaps them if the left one is larger than the right one. One full walk through the list is called a pass.

What actually happens during a pass: On the first pass, the algorithm starts at position 0 and compares every adjacent pair all the way to the end. Every time it finds a pair where the left number is bigger, it swaps them. Here's the key insight: the largest number in the list will win every single comparison it's involved in, so it gets pushed one position to the right each time, all the way to the final position by the end of the pass. This is where the name comes from: the largest value "bubbles up" to the top of the list, the same way an air bubble rises to the surface of water.

Walk through it with real numbers: Start with [5, 1, 4, 2].

Notice two things. First, each pass checks one fewer position than the last, because the end of the list is already sorted. That's why the code uses n - i - 1 as the inner loop boundary. It is not a magic formula, just "don't re-check positions that are already in their final place." Second, pass 3 made zero swaps, which told the algorithm the list was already sorted and it could stop. This early-termination check is important: without it, the algorithm would keep making pointless passes over an already-sorted list.

How fast (or slow) is it:

• Best case, O(n): If the list is already sorted, the algorithm does one pass, sees zero swaps, and stops. That single pass makes n−1 comparisons, so it runs in linear time.
• Worst case, O(n²): If the list is in reverse order (e.g., [5, 4, 3, 2, 1]), every pair needs a swap on every pass, and the algorithm needs the maximum number of passes. For a list of 1,000 items, that's roughly 500,000 comparisons.
• Average case, O(n²): For a randomly shuffled list, Bubble Sort still tends to need most of those passes. This is genuinely slow compared to algorithms like Quick Sort, which averages O(n log n).

How it compares to Selection Sort: Both are O(n²) sorting algorithms, and both are used primarily for teaching. The difference is in how they move data. Selection Sort scans the entire unsorted portion to find the single smallest element, then places it in its final position with one swap. It minimises the number of swaps (at most n−1 total), which matters when writing data is expensive, like on flash storage. Bubble Sort swaps constantly during every pass, but it has a property Selection Sort doesn't: stability. Two elements with equal value will keep their original relative order after sorting. If you sort a class roster by grade and two students both have 85%, Bubble Sort guarantees they stay in whatever order they were in before (say, alphabetical). Selection Sort, as typically implemented, does not make that guarantee.

Where you'll actually see it used: Honestly, almost nowhere in production software. Bubble Sort is one of the slowest general-purpose sorting algorithms. Python's built-in sorted() uses Timsort, which is roughly 1,000× faster on large lists. Bubble Sort survives in every introductory computer science course because it is the easiest sorting algorithm to trace by hand and understand step by step. It builds the mental model you need before tackling recursive algorithms like Quick Sort. It is also a common interview warm-up, not because anyone expects you to use it in real code, but because explaining why it's slow is a good test of whether someone genuinely understands time complexity.

Common mistakes to watch for: (1) Assuming Bubble Sort is always O(n²). With the early-termination check, an already-sorted list finishes in one pass at O(n). (2) Confusing comparisons with swaps. Every pass makes n−i−1 comparisons, but not every comparison causes a swap. (3) Off-by-one errors in the inner loop: forgetting the -1 in n-i-1 and accessing an index that doesn't exist, or forgetting the -i and wastefully re-checking elements already in their final place.

flowchart TD
    Start([Start]) --> A["Start a new pass
through the list"]
    A --> B["Compare two
neighbouring items"]
    B --> C{"Are they in
the wrong order?"}
    C -- Yes --> D["Swap them"]
    C -- No --> E["Leave them as they are"]
    D --> F["Move to the
next pair"]
    E --> F
    F --> G{"Reached the
end of the list?"}
    G -- No --> B
    G -- Yes --> H{"Did you swap
anything this pass?"}
    H -- Yes --> A
    H -- No --> Sorted[("List is sorted!")]
    Sorted --> Stop([Stop])
                        

Where you've already done this: Imagine you're a teacher sorting exam papers into grade ranges. You pick one paper at random (say it scored 65), and you ask a student to help you split the pile: everything below 65 goes to the left, everything 65 and above goes to the right. Now the 65 paper is in its correct position. You repeat this process on the left pile and the right pile separately, picking a new "splitter" paper each time, until every pile has just one paper. That's Quick Sort. It picks a reference value (called the pivot), partitions the list around it, and then recursively sorts the two resulting halves.

Why the pivot matters so much: The entire performance of Quick Sort depends on the pivot choice. If you pick a pivot that splits the data roughly in half, each level of recursion cuts the problem size by 2, giving you about log₂(n) levels with n work at each level, for a total of O(n log n). But if you consistently pick the smallest or largest item as the pivot (which happens if the data is already sorted and you always choose the last element), one side gets everything and the other side gets nothing. That degrades the algorithm to O(n²), the same as Selection Sort or Bubble Sort. In practice, strategies like picking a random pivot or using the "median of three" (comparing the first, middle, and last items and choosing the median) make the worst case extremely unlikely.

Walk through it with real numbers: Start with [8, 3, 1, 7, 0, 10, 2], using the last element as the pivot.

Final sorted result: [0, 1, 2, 3, 7, 8, 10]. Notice that steps 2a and 2b happen independently of each other. This is the divide-and-conquer structure: once the pivot is placed, the left and right sides are completely separate problems.

How fast (or slow) is it:

• Best and average case, O(n log n): When the pivot splits the data reasonably well, each level of recursion processes n items total, and there are about log₂(n) levels. For 1,000 items, that's roughly 10,000 operations instead of the 500,000 that O(n²) sorts require.
• Worst case, O(n²): Happens when the pivot is always the smallest or largest item (e.g., the list is already sorted and you pick the last element). Each partition only removes one element, so you get n levels of recursion instead of log n. In practice, randomised pivot selection makes this case negligibly rare.
• Space: O(log n) on average for the recursive call stack. Each recursive call needs a small amount of memory to remember where to return to. In the worst case, this grows to O(n).

How it compares to the O(n²) sorts: Quick Sort is in a fundamentally different speed class. Selection Sort and Bubble Sort compare every pair of items, so doubling the data quadruples the work. Quick Sort's divide-and-conquer approach means doubling the data only slightly more than doubles the work. For 10,000 items, Bubble Sort makes roughly 50 million comparisons; Quick Sort makes roughly 130,000. That's a 400x difference, and it gets wider as data grows.

Quick Sort is not stable: Like Selection Sort, Quick Sort can change the relative order of equal items during partitioning. If you sort student records by grade and two students both scored 85, their original order may not be preserved. This is why Python chose Timsort (a stable O(n log n) sort) for its built-in sorted() function instead of Quick Sort. Quick Sort's strength is raw average-case speed with minimal extra memory, which is why C's standard library qsort() and many database engines use it.

Where you'll actually see it used: Quick Sort (or variants of it) powers the default sort in C, C++, Java (for primitive types), and many database query engines. It's favoured in systems where average-case speed matters most and memory is limited, because it sorts "in place" without creating a full copy of the data. The Linux kernel uses a Quick Sort variant for certain internal sorting tasks. It is also a foundational interview topic because it combines recursion, partitioning, and complexity analysis into one algorithm.

Common mistakes to watch for: (1) Always picking the last element as the pivot without considering the input data. On already-sorted lists, this produces the O(n²) worst case. Use random pivot selection or median-of-three to avoid it. (2) Confusing the partition() function with the quick_sort() function. Partition does the actual rearranging; quick_sort just calls partition and then recurses on the two halves. (3) Forgetting the base case in the recursion. If you don't stop when low >= high, the function recurses forever and crashes with a stack overflow.

flowchart TD
    Start([Start]) --> A["Pick the last item
as your 'pivot'"]
    A --> B["Mark a boundary
before the first item"]
    B --> C["Look at each item
one by one"]
    C --> D{"Is this item
smaller than\nthe pivot?"}
    D -- Yes --> E["Move it to the left
of the boundary"]
    D -- No --> F["Leave it where it is"]
    E --> G{"More items
to check?"}
    F --> G
    G -- Yes --> C
    G -- No --> H["Place the pivot at
the boundary"]
    H --> I["Repeat everything on
the left group"]
    I --> J["Repeat everything on
the right group"]
    J --> Sorted[("All groups sorted!")]
    Sorted --> Stop([Stop])
                        

Teaching vs picture: The Python uses <= when splitting around the pivot. The moving bars use a strict <. Same idea; tiny difference on equal numbers. Beginners can ignore this.

Where you've already done this: Two teaching assistants each hold a pile of exam papers already sorted by score. You merge them into one sorted pile by always taking the smaller front paper from either pile. Merge Sort does the same on numbers: split until each piece has one item, then merge sorted halves.

Walk through [38, 27, 43, 3]:

vs Quick Sort: Merge Sort guarantees O(n log n) even on already-sorted data, stays stable (equal items keep their order), but needs O(n) extra space for merge buffers. Quick Sort sorts in place with less memory but can hit O(n²) on bad pivots.

flowchart TD
    Start([List longer than 1?]) --> Split["Split in half"]
    Split --> Left["Sort left half"]
    Split --> Right["Sort right half"]
    Left --> Merge["Merge two sorted halves"]
    Right --> Merge
    Merge --> Done([Sorted])
                        

Teaching vs picture: Blue and yellow bars show the left and right halves during a split. Green flash during merge means we are writing the smaller front value.