Timsort

function timsort(arr) {
    const RUN = 32; // Size of runs to be sorted with insertion sort

    // Sort individual subarrays of size RUN
    for (let i = 0; i < arr.length; i += RUN) {
        insertionSortRun(arr, i, Math.min(i + RUN - 1, arr.length - 1));
    }

    // Merge runs using merge sort logic
    for (let size = RUN; size < arr.length; size = 2 * size) {
        for (let left = 0; left < arr.length; left += 2 * size) {
            const mid = left + size - 1;
            const right = Math.min(left + 2 * size - 1, arr.length - 1);

            if (mid < right) {
                mergeRuns(arr, left, mid, right);
            }
        }
    }

    return arr;
}

function insertionSortRun(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
        const temp = arr[i];
        let j = i - 1;

        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

function mergeRuns(arr, left, mid, right) {
    const leftArray = arr.slice(left, mid + 1);
    const rightArray = arr.slice(mid + 1, right + 1);

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

    while (i < leftArray.length && j < rightArray.length) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }

    while (i < leftArray.length) {
        arr[k] = leftArray[i];
        i++;
        k++;
    }

    while (j < rightArray.length) {
        arr[k] = rightArray[j];
        j++;
        k++;
    }
}

How Timsort Works

Timsort combines the best aspects of merge sort and insertion sort. It identifies naturally occurring runs (sorted sequences) in the data and uses insertion sort for small runs, then merges these runs using a merge sort approach.

Algorithm Strategy:

1. Identify Runs: Find naturally sorted sequences in the data
2. Sort Small Runs: Use insertion sort for runs smaller than 32 elements
3. Extend Runs: Grow runs by including adjacent elements that maintain order
4. Merge Runs: Merge sorted runs using merge sort's merging strategy
5. Balanced Merging: Use galloping mode for efficient merging

Key Innovations:

• Adaptive: Takes advantage of existing order in data
• Hybrid approach: Uses best tool for each job (insertion vs merge)
• Stable: Maintains relative order of equal elements
• Galloping: Optimized merging for runs of different sizes

Why Timsort is Special:

• Python's default: Used in Python's sort() and sorted() functions
• Java implementation: Used for Arrays.sort() with objects
• Real-world optimization: Designed for real-world data patterns
• Research-based: Result of extensive empirical analysis

Performance Characteristics:

• Best Case: O(n) when data is already sorted or nearly sorted
• Worst Case: O(n log n) guaranteed, same as merge sort
• Adaptive: Performance improves with partially sorted data
• Stable: Preserves order of equal elements

Real-World Impact:

• Python: Default sorting algorithm since Python 2.2
• Java: Used for sorting arrays of objects
• Android: Platform's default sorting implementation
• Research influence: Changed how we think about sorting algorithms

Design Philosophy: