O(n log n)
—Linearithmic Time
FineThe best possible for comparison-based sorting.
Mental model
Merge sort: split the array in half log n times deep, then merge each level back — touching all n elements per level. Total: n × log n. A small overhead for a perfectly sorted result.
Interactive Visualisation
✂️ Divide & conquer.Keep splitting the array in half until you have individual elements (log n splits). Then merge them back together in sorted order. Each merge level touches all n elements. Total: n × log n — the theoretical best you can do for general comparison-based sorting.
↓ Split (O(log n) levels)
↑ Merge (O(n) per level)
Step 0/6 — Original array — unsorted
42
7
14
3
6
55
28
91
Groups: 1 · Elements/group: 8 · n=8, log₂(8)=3, n·log(n)≈24 ops
n·log(n) grows faster than linear but much slower than n²
824
1664
64384
2562.048k
1k10k
How it scales
n = 8
~24 ops
n = 64
~384 ops
n = 1,024
~10,240 ops
n = 1,000,000
~20,000,000 ops