Timsort Algorithm

What is Timsort?

Timsort is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It was designed to take advantage of real-world data patterns — specifically, partially sorted arrays. Timsort finds and optimizes “runs” (small sorted sequences) in the data and then merges them efficiently.

History

• Developed by Tim Peters in 2002 for Python’s internal sorting.
• Adopted by Java as the underlying algorithm for:
  • Arrays.sort(Object[])
  • Collections.sort(List<T>)

How Timsort Works

1. Identify natural runs: Small sequences of already sorted elements (either ascending or descending).
2. Use Insertion Sort to extend small runs (usually < 32 elements).
3. Merge runs efficiently using a technique similar to Merge Sort.
4. Apply various optimizations for merging to reduce copying and comparison overhead.

Why Timsort?

• Leverages existing order in data → faster than classic O(n log n) sorts in practice.
• Stable: maintains order of equal elements.
• Very efficient for real-world datasets (which often contain sorted subsequences).

When is Timsort Used in Java?

Note: Arrays.sort(int[]) uses Dual-Pivot Quicksort for primitives.

Time & Space Complexity

• Space Complexity: O(n)
• Stable: ✅ Yes

Code Example

import java.util.*;

public class TimsortExample {

    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(
            42, 20, 17, 13, 28, 14, 23, 15
        ));

        System.out.println("Original list:");
        System.out.println(numbers);

        // Timsort is used internally by Collections.sort()
        Collections.sort(numbers);

        System.out.println("Sorted list:");
        System.out.println(numbers);
    }
}

Output

Original list:
[42, 20, 17, 13, 28, 14, 23, 15]
Sorted list:
[13, 14, 15, 17, 20, 23, 28, 42]

Timsort – Visual Explanation (Step-by-Step)

Let’s sort this list:

[42, 20, 17, 13, 28, 14, 23, 15]

Step 1: Identify Runs

Timsort scans and identifies “runs” — sequences already in order:

• Initial run detection (descending or ascending):
  • [42, 20, 17, 13] → reverse to ascending → [13, 17, 20, 42]
  • [28, 14] → reverse to ascending → [14, 28]
  • [23, 15] → reverse → [15, 23]

Now we have 3 ascending runs:

[13, 17, 20, 42], [14, 28], [15, 23]

Step 2: Extend Short Runs (if needed)

If runs are too small (e.g. < 32), Insertion Sort may be used to grow them.

Step 3: Merge Runs

Timsort merges the sorted runs similar to Merge Sort:

• Merge [13, 17, 20, 42] and [14, 28]
  → [13, 14, 17, 20, 28, 42]
• Merge with [15, 23]
  → [13, 14, 15, 17, 20, 23, 28, 42]

Final Sorted List

[13, 14, 15, 17, 20, 23, 28, 42]

Summary

• Timsort combines Insertion Sort for small runs and Merge Sort for merging.
• It is adaptive, efficient for partially sorted data.
• Used internally by Java’s Collections.sort() and Arrays.sort(Object[]).
• Offers O(n log n) performance with best-case O(n) for nearly sorted data.