Skip to content

Timsort (Under the Hood)

Introduction

When you call sort() or sorted(), Python uses an algorithm called Timsort (named after Tim Peters, who wrote it in 2002).

In a system design or algorithmic interview, an interviewer might ask, "What algorithm does Python use to sort, and what is its time complexity?" You must know the basics of Timsort.

How Timsort Works

Timsort is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort.

It is designed to perform exceptionally well on real-world data, which often contains partially sorted subarrays (called "runs").

  1. Scan for Runs: Timsort scans the array looking for consecutive elements that are already ordered (either ascending or strictly descending).
  2. Insertion Sort: If it finds a run that is too small, it uses Insertion Sort to boost it to a minimum size.
  3. Merge Sort: It then uses a highly optimized Merge Sort to merge these ordered runs together.

Time Complexity

Because Timsort capitalizes on existing order in the data, its best-case scenario is much better than a standard Merge Sort.

  • Best Case: \(O(N)\) (if the array is already sorted or reverse-sorted).
  • Average Case: \(O(N \log N)\)
  • Worst Case: \(O(N \log N)\)

Space Complexity

Unlike standard in-place algorithms like Quick Sort (\(O(\log N)\) space), Timsort requires auxiliary memory to merge the runs.

  • Space Complexity: \(O(N)\) worst case.

(Note: While list.sort() modifies the list in place, the Timsort algorithm running under the hood still allocates up to \(O(N)\) temporary memory to perform the merges).

Why not Quick Sort?

Interviewers sometimes ask why Python doesn't use Quick Sort. 1. Predictability: Quick Sort has a worst-case time complexity of \(O(N^2)\). Timsort guarantees \(O(N \log N)\). 2. Stability: Quick Sort is generally unstable. Timsort is stable (which is critical for Python, as discussed in the next section). 3. Real-world data: Timsort is specifically designed to exploit the partial ordering commonly found in real-world application data, yielding \(O(N)\) best-case times.

Summary

  • Python uses Timsort (Merge Sort + Insertion Sort).
  • Time Complexity: \(O(N \log N)\) average/worst, \(O(N)\) best.
  • Space Complexity: \(O(N)\).
  • It is a stable sorting algorithm.