Definition
O(n log n) combines division (log n) with processing (n). It's the theoretical lower bound for comparison-based sorting.
Key Characteristics
- ✓Divide & Conquer complexity
- ✓Limit for efficient sorting
- ✓Slower than O(n), faster than O(n²)
Use Cases
Used in these scenarios:
🔀
Merge Sort
Divide and merge to sort
⚡
Quick Sort
Partition by pivot
🏔️
Heap Sort
Extract max using heap
Complexity
Time Complexity
Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space Complexity
O(n)
Understand Deeper with Visualization
See how the algorithm works through step-by-step animations and code execution.
Start Visualization