CoreSource checked

Tim Sort

Sorts by detecting existing ordered runs and merging them with safeguards for real-world data.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Sorting
Difficulty: Advanced
Family: Hybrid Sort
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 3
Code example: Not ready
Visualization: Ready
Aliases: Timsort

Overview

Tim Sort scans for ascending or descending runs, extends short runs, and merges them while maintaining stack invariants that keep merging efficient and stable.

Core Concepts

comparison rulestable orderingexisting runshybrid strategyhybrid sortordering invariantcomparison or key rulearray rearrangement

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

Use it for stable general-purpose sorting of arrays or lists.
Use it when real-world data may already contain ordered runs.
Use it when predictable library-grade behavior matters more than a tiny implementation.

When Not to Use

Avoid it when an extremely small fixed-size sort can be simpler.
Avoid it when unstable in-place sorting is required with minimal auxiliary memory.
Avoid reimplementing it without carefully testing run-stack invariants.

What It Does

Finds ordered runs in the input
Merges runs while keeping the sort stable

Use Cases

General-purpose language runtimes
Sorting partially ordered data
Stable production sorting

Inputs

Array or list of comparable values

Outputs

Stable sorted collection

Pseudocode

1.Scan for naturally ordered runs
2.Extend short runs with insertion sort
3.Push runs onto a merge stack
4.Merge runs while maintaining balance rules
5.Return the stable sorted result

Canonical Example

Input: array = [1, 2, 3, 7, 6, 5, 8]
Output: [1, 2, 3, 5, 6, 7, 8]
Explanation: The algorithm detects existing runs such as [1,2,3,7] and [6,5], normalizes them, then merges them stably.

Implementation Notes

Detect natural runs before deciding whether to use insertion sort to extend them.
Keep merge invariants explicit and covered by tests.
Use galloping mode only after ordinary merging shows one run winning repeatedly.