How To Do TimSort In JavaScript

TimSort is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It was designed to perform well on real-world data, often containing ordered sequences. TimSort is the default sorting algorithm used in Python and JavaScript (in modern engines like V8), and it is optimized for datasets that are already partially sorted or have patterns like runs (consecutive elements already in order).

In this blog post, we’ll explore how TimSort works, its implementation in JavaScript, and the key concepts that make it efficient. We’ll also discuss its time and space complexities and when you should use TimSort.

What is TimSort?

TimSort was developed by Tim Peters in 2002 for Python and is now widely used in JavaScript’s Array.prototype.sort() method in most modern engines. The algorithm identifies small segments of the array, called runs, that are already sorted. It then uses Insertion Sort to sort small arrays and Merge Sort to combine the runs. This makes it highly efficient when the data has a lot of existing order or partial sorting.

TimSort is designed to minimize the number of comparisons and swaps, making it faster than typical comparison-based algorithms like Quick Sort or Merge Sort in many real-world applications.

procedure TimSort(arr)
    n = length of arr
    minRun = calculateMinRun(n)

    # Step 1: Sort small sub-arrays using Insertion Sort
    for i = 0 to n - 1 in steps of minRun do
        InsertionSort(arr, i, min(i + minRun - 1, n - 1))

    # Step 2: Merge sorted runs using Merge Sort
    size = minRun
    while size < n do
        for left = 0 to n - 1 in steps of 2 * size do
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)
            if mid < right:
                Merge(arr, left, mid, right)
        size = 2 * size

Step-by-Step Explanation:

• Step 1: The array is divided into smaller runs, and each run is sorted using Insertion Sort. The minimum size of each run is determined dynamically.
• Step 2: The sorted runs are merged using Merge Sort, gradually increasing the size of the sorted portions until the entire array is sorted.

Time Complexity of TimSort

• Best Case: O(n)—TimSort performs best with linear time complexity when the input array is already sorted.
• Average Case: O(n log n) – TimSort performs at O(n log n) for most inputs, similar to other efficient sorting algorithms.
• Worst Case: O(n log n) – Even in the worst-case scenario, TimSort guarantees O(n log n) time complexity due to its merging process.

Space Complexity of TimSort

• Space Complexity: O(n) – TimSort requires additional space for merging, as it uses a temporary array during the merge step.

JavaScript Implementation of TimSort

Here’s the JavaScript code to implement a simplified version of TimSort:

// Function to perform Insertion Sort on a subarray
function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Function to merge two sorted subarrays
function merge(arr, left, mid, right) {
    let len1 = mid - left + 1;
    let len2 = right - mid;
    let leftArr = new Array(len1);
    let rightArr = new Array(len2);

    for (let i = 0; i < len1; i++) leftArr[i] = arr[left + i];
    for (let i = 0; i < len2; i++) rightArr[i] = arr[mid + 1 + i];

    let i = 0, j = 0, k = left;
    while (i < len1 && j < len2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < len1) arr[k++] = leftArr[i++];
    while (j < len2) arr[k++] = rightArr[j++];
}

// Utility function to calculate the minimum run size
function calculateMinRun(n) {
    let r = 0;
    while (n >= 64) {
        r |= n & 1;
        n >>= 1;
    }
    return n + r;
}

// Main TimSort function
function timSort(arr) {
    const n = arr.length;
    const minRun = calculateMinRun(n);

    // Step 1: Sort small runs using Insertion Sort
    for (let i = 0; i < n; i += minRun) {
        insertionSort(arr, i, Math.min(i + minRun - 1, n - 1));
    }

    // Step 2: Merge sorted runs using Merge Sort
    for (let size = minRun; size < n; size *= 2) {
        for (let left = 0; left < n; left += 2 * size) {
            const mid = Math.min(left + size - 1, n - 1);
            const right = Math.min(left + 2 * size - 1, n - 1);
            if (mid < right) {
                merge(arr, left, mid, right);
            }
        }
    }
}

// Example usage with a larger array
const arr = [20, 45, 17, 23, 60, 50, 99, 15, 30, 10, 85, 33, 75, 40, 5, 55];
console.log("Original array:", arr);
timSort(arr);
console.log("Sorted array:", arr);

Output:

Original array: [
  20, 45, 17, 23, 60, 50,
  99, 15, 30, 10, 85, 33,
  75, 40,  5, 55
]
Sorted array: [
   5, 10, 15, 17, 20, 23,
  30, 33, 40, 45, 50, 55,
  60, 75, 85, 99
]

Expanded Step-by-Step Walkthrough of TimSort

Let’s walk through the TimSort algorithm using the array:
[20, 45, 17, 23, 60, 50, 99, 15, 30, 10, 85, 33, 75, 40, 5, 55].

We’ll detail the steps, covering how TimSort sorts smaller runs using Insertion Sort and then merges these sorted runs using Merge Sort.

Step 1: Calculate the Minimum Run Size

The first step in TimSort is to determine the minimum run size. This is the size of the smallest subarrays that will be sorted using Insertion Sort. In our example, the array has 16 elements, so the minimum run size will be calculated dynamically using the following function:

function calculateMinRun(n) {
    let r = 0;
    while (n >= 64) {
        r |= n & 1;
        n >>= 1;
    }
    return n + r;
}

For our array of size 16, this function will return 16, meaning the entire array will be divided into runs of approximately 16 elements. Since our array is already small, it won’t be broken down further.

Step 2: Sort Small Runs Using Insertion Sort

Next, TimSort applies Insertion Sort to these small runs. In our case, since the array size is smaller than 64, we can treat the entire array as a single run and apply Insertion Sort to it.

Pass 1 (Initial Array):

[20, 45, 17, 23, 60, 50, 99, 15, 30, 10, 85, 33, 75, 40, 5, 55]

Insertion Sort starts by sorting elements from the second element onwards:

• Compare 20 and 45 – no swap is needed; the array remains the same.
• Compare 45 and 17 – swap 17 with 45 and move 17 into its correct position relative to 20. Array becomes: [17, 20, 45, 23, 60, 50, 99, 15, 30, 10, 85, 33, 75, 40, 5, 55]
• Compare 45 and 23 – swap 23 with 45 and move 23 into its correct position. Array becomes: [17, 20, 23, 45, 60, 50, 99, 15, 30, 10, 85, 33, 75, 40, 5, 55]
• Continue this process for each element in the array. After each comparison, the current element is shifted left into its correct position relative to the sorted part of the array.

Pass 2 (Array after Insertion Sort):

After all the comparisons, Insertion Sort fully sorts the array as: [5, 10, 15, 17, 20, 23, 30, 33, 40, 45, 50, 55, 60, 75, 85, 99]

Now, we have a single sorted run, and since the array size is relatively small, there’s no need for additional passes.

Step 3: Merge Runs Using Merge Sort

TimSort would typically continue to merge small sorted runs into larger ones using Merge Sort. However, no merging is necessary since our array is already sorted after the first pass with Insertion Sort. TimSort would repeatedly merge adjacent runs for larger arrays with more runs until the entire array is fully sorted.

If we had multiple runs, Merge Sort would:

1. Compare and merge adjacent runs into larger sorted subarrays.
2. Continue merging until the entire array is sorted.

Let’s break down what would happen with multiple runs:

Example of Merging Two Sorted Runs:

Assume we have two sorted runs:
[5, 17, 23, 50] and [10, 20, 30, 45].

Merge Sort will compare elements from both runs and merge them into a single sorted array:

• Compare 5 and 10 → take 5.
• Compare 17 and 10 → take 10.
• Compare 17 and 20 → take 17.
• Continue this process until all elements from both runs are merged into a single sorted run.

The merged result:
[5, 10, 17, 20, 23, 30, 45, 50]

Step 4: Final Sorted Array

After the Insertion Sort step, our entire array is already sorted as: [5, 10, 15, 17, 20, 23, 30, 33, 40, 45, 50, 55, 60, 75, 85, 99]

No further merging is required, and the process is complete.

Pros and Cons of Using TimSort

Pros:

1. Efficient for Real-World Data: TimSort is particularly fast for datasets that contain ordered or nearly ordered sequences, making it suitable for real-world applications.
2. Stable Sort: TimSort preserves the relative order of elements with equal values, making it a stable sorting algorithm.
3. Adaptive to Input: TimSort is adaptive, meaning it performs better on data that is already partially sorted.

Cons:

1. Slightly More Complex: TimSort is more complex to implement than basic algorithms like Quick Sort or Insertion Sort.
2. Space Overhead: TimSort uses additional space for the merging process, which may not be ideal in memory-constrained environments.

When to Use TimSort

TimSort is an ideal sorting algorithm when:

1. You have partially sorted or nearly sorted data: Since TimSort is designed to handle ordered sequences efficiently, it’s perfect for real-world data that often has some ordering.
2. You need a stable sorting algorithm: TimSort ensures that the relative order of elements is preserved, making it suitable for datasets where stability matters.
3. You need an adaptive sorting algorithm: TimSort adapts to the existing order in the data, making it faster in practice than other O(n log n) algorithms.

Conclusion

TimSort is a highly efficient and adaptive sorting algorithm designed for real-world data. By combining the strengths of Insertion Sort and Merge Sort, TimSort performs exceptionally well on datasets that contain ordered sequences. Its stability, adaptability, and efficient handling of partially sorted data make it valuable in any developer’s toolbox.

Congratulations on reading to the end of the tutorial!

Read the following articles to learn how to implement TimSort:

In Python – How to do TimSort in Python

In C++ – How to Do TimSort in C++

in Rust – How to do TimSort in Rust

Have fun and happy researching!