Introduction
Sorting rearranges elements of a collection into a defined order (usually ascending or descending). It is one of the most fundamental operations in computer science because many algorithms (binary search, deduplication, greedy scheduling) assume sorted input. Sorting algorithms are compared using time complexity, space complexity, stability (whether equal elements retain their relative order), and whether they operate in-place.
Cricket analogy: Arranging a season's batting averages from highest to lowest is sorting, and since algorithms like finding the top-10 assume the list is already ordered, comparing sort methods by speed, memory use, whether tied averages keep their original order (stability), and whether it's done on the same scoreboard (in-place) matters.
Algorithm/Syntax
# Common built-in sorting in Python uses Timsort: O(n log n), stable
arr = [5, 2, 9, 1, 5, 6]
sorted_arr = sorted(arr) # returns a new list
arr.sort() # sorts in place
arr.sort(key=lambda x: -x) # custom key, descending
print(sorted_arr, arr)Explanation
Sorting algorithms fall into two broad families: comparison-based sorts (bubble, insertion, selection, merge, quick, heap sort) which are bounded below by O(n log n) in the average/worst case, and non-comparison sorts (counting, radix, bucket sort) which can achieve O(n+k) by exploiting known value ranges. Simple quadratic sorts like bubble, insertion, and selection sort run in O(n^2) but are easy to implement, stable (bubble/insertion), and efficient for small or nearly-sorted inputs. Python's built-in sort uses Timsort, a hybrid of merge sort and insertion sort that is stable and runs in O(n log n) worst case, O(n) best case for nearly sorted data.
Cricket analogy: Bubble sort repeatedly swapping adjacent batsmen's scores until sorted is a comparison-based O(n^2) method, easy but slow for a big squad, whereas a specialized 'by run bracket' sort exploiting known score ranges could hit O(n+k); Python-style Timsort, a hybrid merge-insertion sort, is how most scoreboard software actually stably sorts near-final rankings in O(n log n) worst case.
Example
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Trace: [5, 2, 9, 1]
# i=1: key=2, shift 5 -> [5,5,9,1] -> place 2 -> [2,5,9,1]
# i=2: key=9, no shift -> [2,5,9,1]
# i=3: key=1, shift 9,5,2 -> [2,5,9,9] -> [2,5,5,9] -> [2,2,5,9] -> place 1 -> [1,2,5,9]
print(insertion_sort([5, 2, 9, 1])) # [1, 2, 5, 9]Complexity
Bubble sort: O(n^2) time, O(1) space, stable. Selection sort: O(n^2) time, O(1) space, NOT stable (swaps can move equal elements past each other). Insertion sort: O(n^2) worst, O(n) best (nearly sorted), O(1) space, stable, and efficient online (can sort as data arrives). These are typically used for small arrays or as the base case inside hybrid algorithms like Timsort and Introsort.
Cricket analogy: Bubble sort reordering batsmen is O(n^2) but stable, selection sort picking the minimum each pass is O(n^2) but unstable since swaps can leapfrog tied averages, and insertion sort is O(n^2) worst but O(n) best for an already-nearly-sorted lineup and stable, which is why small squads or hybrid ranking tools use insertion sort as their base case.
Key Takeaways
- Comparison sorts cannot beat O(n log n) worst-case time in general.
- Stability matters when sorting records by a secondary key after a primary key.
- Insertion sort is efficient for small or nearly-sorted arrays and is used inside Timsort/Introsort.
- Non-comparison sorts (counting, radix) beat O(n log n) only when the value range is bounded.
Practice what you learned
1. Which of these is a property of a stable sort?
2. What is the time complexity lower bound for comparison-based sorting in the worst case?
3. Which sorting algorithm does Python's built-in sort() use?
4. Which of the following sorts is NOT stable in its typical implementation?
5. When is insertion sort a good practical choice?
Was this page helpful?
You May Also Like
Quicksort and Mergesort
Deep dive into two classic divide-and-conquer sorts: quicksort's in-place partitioning and mergesort's stable merging.
Heap Sort and Counting Sort
How heap sort uses a binary heap for guaranteed O(n log n) in-place sorting, and how counting sort achieves linear time for bounded integers.
Big-O Notation
A precise guide to Big-O notation and the common complexity classes every developer must recognize.