All courses › Intermediate Programming › Sorting and search

Sorting and search

Comparison-based sorting can at best be done in O(nlog⁡n)O(n\log n), which Python's built-in Timsort achieves. If a list is already sorted, binary search gives fast lookup by repeatedly halving the search space.

O(nlog⁡n)O(n\log n)best possible complexity for comparison-based sorting
O(log⁡n)O(\log n)binary search in a sorted list

Symbols

nnnumber of elements

Example

Binary search in a sorted list of 4095 elements needs at most ⌈log⁡2(4096)⌉=12\lceil\log_2(4096)\rceil = 12 comparisons.

Binary search requires the list to be sorted beforehand — otherwise it gives a wrong answer without warning.
Practise algorithms and data structures for free →

← Stack and queue · NumPy array and vectorization →

Part of Intermediate Programming: Algorithms and data structures.