Sorting Algorithms

From bubble sort to Tim sort, why algorithm choice matters

Sorting is one of the most studied problems in CS, and for good reason. Nearly every other algorithm works better on sorted data.
Common sorting algorithms:
| Algorithm | Time (avg) | Space | Stable? ||-----------|-----------|-------|---------|| Bubble Sort | O(n²) | O(1) | Yes || Selection Sort | O(n²) | O(1) | No || Insertion Sort | O(n²) / O(n) best | O(1) | Yes || Merge Sort | O(n log n) | O(n) | Yes || Quick Sort | O(n log n) avg | O(log n) | No || Tim Sort (Python) | O(n log n) | O(n) | Yes |

Insertion sort, simple and efficient for small/nearly-sorted datapython

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Shift elements greater than key one position right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 2, 4, 6, 1, 3]))  # → [1, 2, 3, 4, 5, 6]

🐍In the Real World...

Python's built-in sorted() uses TimSort, a hybrid of merge sort and insertion sort. It's O(n log n) worst case and O(n) for already-sorted data. You almost never need to implement sorting yourself.

🤔Quick Check

For a nearly-sorted array (only a few elements out of place), which sorting algorithm is most efficient?

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Sort Colors (Dutch Flag)

Sort an array of 0s, 1s, and 2s in-place in one pass. (Dutch National Flag problem)
Expected output: [0, 0, 1, 1, 2, 2]

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next