AlgoViz: Interactive Algorithm Visualization Tool

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.

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?