Tim Sort Visualizer: Step-by-Step Animation & Complexity

Tim Sort

Category: Sorting | Time: O(n log n) | Space: O(n)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Tim Sort

A hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language.

Code Editor

The code is for reference. Editing it won't affect the visualization.

const RUN = 32;

// Insertion sort for sub-arrays
function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
        let temp = arr[i];
        let j = i - 1;
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

// Merge function to merge sorted runs
function merge(arr, l, m, r) {
    let len1 = m - l + 1, len2 = r - m;
    let left = new Array(len1);
    let right = new Array(len2);
    for (let i = 0; i < len1; i++)
        left[i] = arr[l + i];
    for (let i = 0; i < len2; i++)
        right[i] = arr[m + 1 + i];

    let i = 0, j = 0, k = l;

    while (i < len1 && j < len2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < len1) {
        arr[k] = left[i];
        k++;
        i++;
    }

    while (j < len2) {
        arr[k] = right[j];
        k++;
        j++;
    }
}

// Main Tim Sort function
function timSort(arr) {
    let n = arr.length;
    // Sort individual sub-arrays of size RUN
    for (let i = 0; i < n; i += RUN) {
        insertionSort(arr, i, Math.min((i + RUN - 1), (n - 1)));
    }

    // Start merging from size RUN. It will merge
    // to form size 2*RUN, then 4*RUN, 8*RUN and so on
    for (let size = RUN; size < n; size = 2 * size) {
        for (let left = 0; left < n; left += 2 * size) {
            let mid = left + size - 1;
            let right = Math.min((left + 2 * size - 1), (n - 1));
            if(mid < right) {
              merge(arr, left, mid, right);
            }
        }
    }
    return arr;
}

Frequently Asked Questions

About Tim Sort

What is Tim Sort?

How does Tim Sort work?

What is the time complexity of Tim Sort?

Why is Tim Sort so popular in practice?

What is a 'minrun' in Tim Sort?

What is 'galloping' in Tim Sort's merge step?

Is Tim Sort an in-place algorithm?

Why does Tim Sort use Insertion Sort?

How does Tim Sort maintain stability?

Can Tim Sort's performance degrade?

Where can I learn more?