Tim Sort in Python

Last Updated : 31 May, 2024

Sorting is a fundamental operation in computer science, used in a variety of applications from data analysis to algorithms optimization. One such efficient and widely used sorting algorithm is Tim Sort. Created by Tim Peters in 2002, Tim Sort is the default sorting algorithm in Python and is renowned for its speed and efficiency in real-world data scenarios.

What is Tim Sort?

Tim Sort is a hybrid sorting algorithm derived from merge sort and insertion sort. It is designed to perform well on many kinds of real-world data. Tim Sort’s efficiency comes from its ability to exploit the structure present in the data, such as runs (consecutive sequences that are already ordered) and merges these runs using a modified merge sort approach.

How Tim Sort Works?

Identify Runs: The algorithm first scans the list to identify runs, which are sequences of consecutive elements that are either ascending or descending. If a run is descending, Tim Sort reverses it to make it ascending.
Use Insertion Sort: For small runs (default size 32 or less), Tim Sort uses insertion sort to order the elements. Insertion sort is efficient for small datasets and nearly sorted datasets.
Merge Runs: Once the list is divided into sorted runs, Tim Sort uses a modified merge sort to merge these runs together, ensuring stability and efficiency.
Galloping Mode: An optimization used during merging to quickly merge runs when one run’s elements are much larger than the other’s.

Why Tim Sort is Efficient?

Exploitation of Natural Runs: By identifying and using already sorted sequences, Tim Sort minimizes the number of comparisons and swaps.
Hybrid Approach: Combining insertion sort for small sequences and merge sort for larger sequences ensures efficiency.
Stability: Tim Sort maintains the relative order of equal elements, making it stable.

Tim Sort in Python:

Tim Sort is the default sorting algorithm in Python’s sort() method for lists and sorted() function. Here’s how you can use it:

Python

# Using the sort() method
my_list = [5, 3, 1, 4, 6, 2]
my_list.sort()
print("Sorted list using sort():", my_list)

# Using the sorted() function
my_list = [5, 3, 1, 4, 6, 2]
sorted_list = sorted(my_list)
print("Sorted list using sorted():", sorted_list)

Output

Sorted list using sort(): [1, 2, 3, 4, 5, 6]
Sorted list using sorted(): [1, 2, 3, 4, 5, 6]

Complete Implementation of Time Sort in Python:

The Tim Sort algorithm first divides the input array into smaller segments of size min_run and performs an insertion sort on each segment. It then starts merging the sorted segments, doubling the merge size in each iteration until the entire array is merged.

The key steps are:

Initialize the minimum run size (min_run) to 32.
Traverse the array in steps of min_run and perform insertion sort on each segment.
Start merging the sorted segments, doubling the merge size in each iteration.
Return the sorted array.

Implementation:

Python

def insertion_sort(arr, left=0, right=None):
    # Base case: if the array is already sorted, do nothing
    if right is None:
        right = len(arr) - 1

    # Iterate through the array, starting from the second element
    for i in range(left + 1, right + 1):
        # Select the current element
        key_item = arr[i]

        # Compare the current element with the previous one
        j = i - 1

        # While the previous element is greater than the current one,
        # shift the previous element to the next position
        while j >= left and arr[j] > key_item:
            arr[j + 1] = arr[j]
            j -= 1

        # Once the loop ends, the previous element is less than or equal to
        # the current element, so place the current element after it
        arr[j + 1] = key_item

    return arr


def merge(left, right):
    # If the left subarray is empty, return the right subarray
    if not left:
        return right

    # If the right subarray is empty, return the left subarray
    if not right:
        return left

    # Compare the first elements of the two subarrays
    if left[0] < right[0]:
        # If the first element of the left subarray is smaller,
        # recursively merge the left subarray with the right one
        return [left[0]] + merge(left[1:], right)
    else:
        # If the first element of the right subarray is smaller,
        # recursively merge the right subarray with the left one
        return [right[0]] + merge(left, right[1:])


def tim_sort(arr):
    # Initialize the minimum run size
    min_run = 32

    # Find the length of the array
    n = len(arr)

    # Traverse the array and do insertion sort on each segment of size min_run
    for i in range(0, n, min_run):
        insertion_sort(arr, i, min(i + min_run - 1, (n - 1)))

    # Start merging from size 32 (or min_run)
    size = min_run
    while size < n:
        # Divide the array into merge_size
        for start in range(0, n, size * 2):
            # Find the midpoint and endpoint of the left and right subarrays
            midpoint = start + size
            end = min((start + size * 2 - 1), (n - 1))

            # Merge the two subarrays
            merged_array = merge(arr[start:midpoint], arr[midpoint:end + 1])

            # Assign the merged array to the original array
            arr[start:start + len(merged_array)] = merged_array

        # Increase the merge size for the next iteration
        size *= 2

    return arr
  
  
 # Using the sorted() function
my_list = [5, 3, 1, 4, 6, 2]
sorted_list = tim_sort(my_list)
print("Sorted list using Tim Sort:", sorted_list)

Output

Sorted list using Tim Sort: [1, 2, 3, 4, 5, 6]

Time complexity: O(n log n) in the average and worst cases, making it an efficient sorting algorithm for large input arrays.
Auxiliary space: O(n) as the algorithm needs to create new arrays to store the merged results during the merge step.