Sorting Algorithms

What is this?

These are the step-by-step recipes a computer follows to put things in order. Bubble Sort is the simplest — keep swapping neighbours that are out of order, like nudging books one slot at a time. Merge Sort is smarter — split the pile in half, sort each half, then zip them back together. Working through them by hand shows why one is slow and the other fast.

💡 Fun fact: Merge sort was described by John von Neumann back in 1945, making it one of the oldest algorithms still in everyday use.

🔓 Sign in free to read the deep dives. Sign in with Google or Microsoft to start solving.

Core idea: Before you reach for a library sort, understand what one is doing. Two algorithms anchor the spectrum: Bubble Sort, the simplest possible idea — repeatedly swap out-of-order neighbours until nothing moves — and Merge Sort, the canonical divide-and-conquer sort that splits the array in half, sorts each half, and merges them back in order. One is O(n²); the other is O(n log n). Seeing why is the whole lesson.

The pattern

Every comparison sort is a strategy for moving each element past the ones it should sit behind. Bubble Sort does it one tiny adjacent swap at a time, so a single far-out element can take a full pass to drift home — that quadratic cost is the price of only ever looking at neighbours. Merge Sort instead divides the work: recursively halve until pieces are trivially sorted, then merge sorted runs by walking two pointers and always taking the smaller front. Merging n elements is linear, the recursion is log n deep, so the total is O(n log n). The merge step also never reorders equal keys — that is what makes Merge Sort stable.

The problems

These are algorithm walkthroughs, not LeetCode problems — implement each by hand to feel the cost.

• Bubble Sort — repeatedly sweep the array swapping adjacent out-of-order pairs; after pass k the largest k elements are parked at the end. Add an "early exit if no swaps" check to handle nearly-sorted input in one pass. O(n²) time, O(1) space, stable.
• Merge Sort — split the array at the midpoint, recursively sort both halves, then merge the two sorted halves with a linear two-pointer scan. O(n log n) time, O(n) auxiliary space, stable. It is the reference example of divide-and-conquer.

Key takeaways

• Bubble Sort = adjacent swaps; intuitive but O(n²) — useful only as a teaching baseline.
• Merge Sort = divide-and-conquer; split, sort halves, merge — a guaranteed stable O(n log n).
• The merge step is the heart of it — linearly combining two sorted runs reappears everywhere, including the next chapter.
• Why it matters: knowing how sorting works lets you reason about stability, custom orderings, and when a built-in sort is or isn't enough.

Order: Bubble Sort → Merge Sort.