Tim Sort: The Default Sorting Algorithm in Python

Updated: at 05:33 AM

Tim Sort is a highly efficient, adaptive sorting algorithm used in Python and other programming languages. As the default sorting algorithm for Python’s sorted() function and list.sort() method, Tim Sort combines the advantages of Merge Sort and Insertion Sort to deliver optimal performance on real-world data.

In this comprehensive guide, we will cover the following topics:

Table of Contents

Open Table of Contents

Overview of Tim Sort

Tim Sort is a hybrid stable sorting algorithm derived from Merge Sort and Insertion Sort. It was designed and implemented by Tim Peters in 2002 for use in Python. The algorithm has the following main properties:

The core idea behind Tim Sort is to analyze the input data and choose the most efficient sorting technique dynamically. It divides the array into smaller subarrays called “runs” that are individually sorted using Insertion Sort. These pre-sorted runs are then merged intelligently to produce the final sorted array.

Let’s look at how Tim Sort achieves this in detail.

How Tim Sort Works

Tim Sort involves three key steps:

  1. Divide the array into “runs” or sorted subsequences
  2. Sort the divided runs using Insertion Sort
  3. Merge the runs in a sorted order

Dividing the Array into Runs

Tim Sort does not blindly split the array into fixed-size chunks. Instead, it intelligently identifies consecutive elements that are already in order and collects them into runs.

This is achieved by iterating through the array from left to right, comparing adjacent elements, and extending the run as long as elements are in order. Once an out-of-order element is found, the run is ended.

For example:

array = [8, 6, 4, 10, 9, 11, 15, 13, 12, 14]

This array would be divided into following runs:

[8] , [6] , [4] , [10, 9, 11] , [15, 13, 12, 14]

The maximum size of a run is chosen to ensure optimal performance of the subsequent Insertion Sort on each run (typically 32 - 64 elements).

Merging the Runs

Once the runs are identified, they are individually sorted using Insertion Sort. Insertion Sort performs very well on small arrays and keeps the runs stable.

The sorted runs are then merged together to build the final sorted array. A standard double-pointer Merge operation is applied, comparing elements from each run and writing the next smallest into the target array.

For example, merging our previous runs would result in:

[4, 6, 8] , [9, 10, 11] , [12, 13, 14, 15]

Tim Sort keeps track of the sizes of the runs to determine the most efficient merge order. By merging runs of increasing sizes, it minimizes the need to repeatedly move elements already in place.

Insertion Sort for Small Runs

Tim Sort uses Insertion Sort to sort individual runs. Insertion Sort is highly efficient for small arrays, as it is adaptive and stable.

The pseudocode for Insertion Sort within Tim Sort is:

for i ← 1 to length(run) - 1
  j ← i
  while j > 0 and run[j] < run[j-1]
    swap run[j] and run[j-1]
    j ← j - 1

This allows Tim Sort to take advantage of existing order in small runs while sorting them stably.

Pseudocode for Tim Sort

The high-level steps in Tim Sort are:

timSort(array):

  runs[] ← identifyRuns(array)

  for each run in runs:
    insertionSort(run)

  result[] ← mergeRuns(runs[])

  return result[]

Where:

The detailed pseudocode is:

initialize minRun = 32

identifyRuns(array, minRun):

  runStart ← 0
  runEnd ← 0

  for i ← 0 to length(array) - 1:

    // extend the run as long as ascending order is maintained
    if i == length(array) - 1 or array[i] > array[i+1]:
      runEnd ← i
      if runEnd - runStart > minRun:
        runs.add(array[runStart...runEnd])
      runStart ← i + 1

  // catch the final run
  if runStart < length(array):
    runs.add(array[runStart..end])

  return runs


insertionSort(run):

  for i ← 1 to length(run) - 1
    j ← i

    while j > 0 and run[j] < run[j-1]
      swap run[j] and run[j-1]
      j ← j - 1


mergeRuns(runs[]):

  result ← new array

  while runs are not empty:

    // find smallest run to merge
    min ← index of smallest run
    other ← index of next smallest run

    while min and other runs are not empty:

      if runs[min].peek() <= runs[other].peek():
        result.add(runs[min].pop())
      else:
        result.add(runs[other].pop())

    // remove empty run
    if runs[min] is empty:
      runs.remove(min)
    else:
      runs.remove(other)

  return result

This covers the essential logic behind Tim Sort’s adaptive, stable sorting technique.

Comparison with Other Sorting Algorithms

How does Tim Sort compare against other common sorting algorithms like Quick Sort, Merge Sort, and Heap Sort?

Tim Sort combines the advantages of Merge Sort and Insertion Sort to achieve optimal real-world performance. The table below summarizes the key differences:

AlgorithmTime ComplexitySpace ComplexityStableAdaptive
Tim SortBest O(n), Avg O(n log n)O(n)YesYes
Quick SortAvg O(n log n), Worst O(n2)O(log n)NoNo
Merge SortO(n log n)O(n)YesNo
Heap SortO(n log n)O(1)NoNo

Tim Sort balances all factors - speed, stability, space usage, and real-world adaptivity to provide superior performance for Python.

Time and Space Complexity Analysis

The time and space complexity of Tim Sort depends on the structure of the input array:

So in summary, Tim Sort provides:

Its adaptivity allows it to approach linear time for partially ordered real-world data.

Applications and Use Cases of Tim Sort

Tim Sort is ideally suited for situations where:

Key examples include:

Overall, Tim Sort should be preferred over Quick Sort and Merge Sort for optimal real-world performance and stability in sorting tasks involving large arrays or complex data.

Common Mistakes and How to Avoid Them

Here are some common mistakes developers make when using or implementing Tim Sort:

Carefully following Tim Sort’s adaptive merging strategy and using appropriate run sizes will help avoid these pitfalls.

Implementing Tim Sort in Python

Python uses Tim Sort internally for its sorted(), list.sort(), and other methods. But Tim Sort can also easily be implemented manually:

def tim_sort(array):

  min_run = 32
  n = len(array)

  # identify Runs
  runs = []
  new_run = [array[0]]
  for i in range(1, n):
    if array[i] >= array[i-1]:
      new_run.append(array[i])
    else:
      runs.append(new_run)
      new_run = [array[i]]
  runs.append(new_run)

  # insertion Sort runs
  for run in runs:
    for i in range(1, len(run)):
      j = i
      while j > 0 and run[j] < run[j-1]:
        run[j], run[j-1] = run[j-1], run[j]
        j -= 1

  # merge runs
  sorted_array = []
  min_run = min(len(r) for r in runs)
  while runs:
    a = runs[0]
    b = runs[1]
    runs.pop(0)
    for _ in range(min(len(a), len(b))):
      if a[0] <= b[0]:
        sorted_array.append(a.pop(0))
      else:
        sorted_array.append(b.pop(0))
    if a:
      runs.append(a)
    if b:
      runs.append(b)

  return sorted_array

This demonstrates the key steps to implement Tim Sort efficiently in Python.

Conclusion

Tim Sort is an extremely effective sorting algorithm that optimizes real-world performance by adapting to input data structure. By combining Merge Sort and Insertion Sort, it delivers speed, stability, and efficiency across inputs.

Key takeaways include:

Tim Sort’s practical adaptivity makes it ideal as the default sorting method in Python and other languages. With some care, developers can easily implement and apply Tim Sort for a variety of efficient sorting tasks.