Timsort Implementation in Python

Timsort is a highly optimized sorting algorithm that is widely used in programming languages such as Python, Java, and C++. Timsort is a hybrid sorting algorithm, meaning that it uses both comparison-based and non-comparison-based sorting techniques to achieve high efficiency. It was designed to perform well on many different kinds of real-world data, including data with natural ordering patterns, such as runs and clusters.

How Timsort Algorithm Works?

The Timsort algorithm can be summarized in the following steps:

1. Divide the input list into small pieces called runs. Each run is sorted using insertion sort or a binary insertion sort.
2. Merge the runs together using a merge sort algorithm.
3. Repeat the above steps until the entire list is sorted.

The algorithm works by dividing the input list into smaller runs that are already sorted or nearly sorted. The length of the runs is determined by finding subsequences that are either increasing or decreasing. The algorithm uses a stack data structure to keep track of the runs and their lengths, and it merges the runs together as needed to create longer sorted runs.

Timsort Algorithm Implementation in Python

Here’s an implementation of the Timsort algorithm in Python:

def insertion_sort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    for i in range(left + 1, right + 1):
        key_item = arr[i]
        j = i - 1
        while j >= left and arr[j] > key_item:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key_item

    return arr


def merge(left, right):
    if not left:
        return right

    if not right:
        return left

    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)

    return [right[0]] + merge(left, right[1:])


def timsort(arr):
    min_run = 32
    n = len(arr)

    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))

    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            midpoint = start + size - 1
            end = min((start + size * 2 - 1), (n-1))
            merged_array = merge(
                left=arr[start:midpoint + 1],
                right=arr[midpoint + 1:end + 1]
            )
            arr[start:start + len(merged_array)] = merged_array

        size *= 2

    return arr

The above code implements the Timsort algorithm in Python. The insertion_sort() function is used to sort the small runs of the input list, and the merge() function is used to merge the sorted runs together. The timsort() function uses a minimum run size of 32 elements and iteratively divides the input list into runs of that size or smaller using the insertion_sort() function. The sorted runs are then merged together using the merge() function until the entire list is sorted.

Time and Space Complexity

The time complexity of the Timsort algorithm is O(n log n) in the worst case, which occurs when the input list is not already partially sorted. However, in the best case, when the input list is partially sorted or nearly sorted, the algorithm can have a time complexity of O(n), as it skips the sorting step and goes straight to the merging step. The space complexity of the Timsort algorithm is O(n), as it requires additional memory to store the stack of runs and the merged output array.

One Example Run

Let’s run an example of the Timsort algorithm on an input list of integers to see how it works:

arr = [6, 2, 8, 1, 5, 9, 4, 3, 7]
sorted_arr = timsort(arr)

print(sorted_arr)

The output of the above code will be:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

In this example, we start with an input list of integers [6, 2, 8, 1, 5, 9, 4, 3, 7]. The timsort() function first divides the input list into small runs of length 32 or less using the insertion_sort() function. In this case, the input list is small enough that it is sorted as a single run using the insertion_sort() function. The sorted run is then merged with the other sorted runs using the merge() function until the entire input list is sorted.

Conclusion

The Timsort algorithm is a highly efficient sorting algorithm that combines the strengths of insertion sort and merge sort to achieve high performance on a wide variety of input data. Its ability to handle partially sorted or nearly sorted data efficiently makes it a popular choice in programming languages such as Python, Java, and C++. The Timsort algorithm has a worst-case time complexity of O(n log n) and a space complexity of O(n).