Algorithms // Data Structures

SORTING &
BIG O NOTATION

Organizing chaotic data into sequential order is one of the most thoroughly studied problems in computer science. How you sort your data dictates how fast your database can search, query, and retrieve information.

Time Complexity

Not all algorithms are created equal. We measure the efficiency of an algorithm using Big O Notation, which describes how the runtime scales as the dataset grows larger.

O(n^2)

Quadratic. As data doubles, time quadruples. (Bubble, Insertion, Selection)

O(n \log n)

Linearithmic. The mathematical speed limit for comparative sorting. (Quick, Merge)

Divide and Conquer

The $O(n^2)$ algorithms waste time comparing elements that are already relatively sorted. To reach $O(n \log n)$ speeds, we must use recursion.

Merge Sort works by recursively halving the array until every element is isolated. Then, it "merges" them back together, sorting them perfectly as it zips the halves up.

Try running Selection Sort, randomizing the array, and then running Merge Sort. The difference in speed and strategy is incredibly obvious when visualized.

Sorting Visualizer

Efficiency Comparison

Pivot / Min

Comparing

Swapping / Merging

Sorted

Further Optimization

Move beyond comparative sorting to explore memory constraints and integer keys.

Heap Sort

Utilizes a binary heap data structure to continuously extract the maximum element.

Radix Sort

A non-comparative integer sorting algorithm that sorts data with integer keys by grouping digits.