Learn computing fundamentals, programming, algorithms, systems, and software engineering.
Sorting arranges data into order so that it can be searched and processed efficiently. The simple sorting algorithms — bubble, insertion, and selection — are easy to understand and run in O(n^2) time, which is fine for small lists but becomes impractical at scale. The divide-and-conquer algorithms, merge sort and quick sort, split the problem in half repeatedly and combine sorted pieces, giving O(n log n) performance. Merge sort is stable and predictable: it divides the list into single elements, then merges them back in sorted order. Quick sort picks a pivot and partitions the list into elements smaller and larger than the pivot, then sorts each side. Merge sort is guaranteed O(n log n) in the worst case, while naive quick sort can degrade to O(n^2) on already-sorted input if the pivot is chosen poorly. Searching falls into two families. Linear search walks the list from beginning to end in O(n). Binary search is far faster, O(log n), but it only works on sorted data: it looks at the middle, and if the target is smaller it searches the left half, otherwise the right half. In practice Python provides sorted() and list.sort() (both O(n log n)) and the bisect module for binary search. Understanding the underlying algorithms, though, is what lets you choose the right tool and reason about performance.
| Linear search | Binary search | |
|---|---|---|
| Requirement | None | Data must be sorted |
| Method | Check every element | Halve the range each step |
| Time | O(n) | O(log n) |
| Best for | Small or unsorted data | Large sorted data |
| Algorithm | Best | Average | Worst | Stable |
|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | No |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | No |
sorted() returns a new list and leaves the original unchanged; list.sort() modifies the list in place and returns None.
Build the sorted result one element at a time by inserting each item into its correct position.
[1, 2, 3, 4]
On a sorted list, check the middle and discard half the range each step.
4
Linear search works on unsorted data; binary search is much faster but needs sorted input.
1 -1