Tim Sort Algorithm

Introduction to 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 first divides the array into small chunks and then sorts those chunks using insertion sort. Finally, it merges the sorted chunks using merge sort. Tim sort is used in Python's built-in sort() function and has a time complexity of O(n log n) in the worst case.

---

Step-by-Step Process

Consider an array with the following elements:

[5, 21, 7, 23, 19, 0, 17, 22, 11, 13]

To sort this array using Tim sort, follow these steps:

1. Divide the Array: Divide the array into small chunks (known as 'runs'). The size of the runs is determined by a value called 'MIN_RUN'.
2. Sort Each Run: Sort each run using insertion sort.
3. Merge Runs: Merge the sorted runs using merge sort to produce the final sorted array.

Let's apply these steps to the example array:

• Initial array: [5, 21, 7, 23, 19, 0, 17, 22, 11, 13]
• Divide into runs (assuming MIN_RUN=4): [5, 21, 7, 23], [19, 0, 17, 22], [11, 13]
• Sort each run using insertion sort: [5, 7, 21, 23], [0, 17, 19, 22], [11, 13]
• Merge runs using merge sort: [0, 5, 7, 11, 13, 17, 19, 21, 22, 23]

---

Pseudo Code for Tim Sort

Below is the pseudo code for the Tim sort algorithm:

function timSort(array)
    n = length(array)
    minRun = calculateMinRun(n)
    for start = 0 to n do
        end = min(start + minRun - 1, n - 1)
        insertionSort(array, start, end)
    end for
    size = minRun
    while size < n do
        for start = 0 to n do
            mid = min(start + size - 1, n - 1)
            end = min((start + 2 * size - 1), (n - 1))
            if mid < end then
                merge(array, start, mid, end)
            end if
        end for
        size = size * 2
    end while
end function

function calculateMinRun(n)
    r = 0
    while n >= 64 do
        r |= n & 1
        n >>= 1
    end while
    return n + r
end function

function insertionSort(array, left, right)
    for i = left + 1 to right do
        key = array[i]
        j = i - 1
        while j >= left and array[j] > key do
            array[j + 1] = array[j]
            j -= 1
        end while
        array[j + 1] = key
    end for
end function

function merge(array, left, mid, right)
    len1, len2 = mid - left + 1, right - mid
    leftArray, rightArray = array[left:left + len1], array[mid + 1:mid + 1 + len2]
    i, j, k = 0, 0, left
    while i < len1 and j < len2 do
        if leftArray[i] <= rightArray[j] then
            array[k] = leftArray[i]
            i += 1
        else
            array[k] = rightArray[j]
            j += 1
        end if
        k += 1
    end while
    while i < len1 do
        array[k] = leftArray[i]
        i += 1
        k += 1
    end while
    while j < len2 do
        array[k] = rightArray[j]
        j += 1
        k += 1
    end while
end function

Explanation:

• Calculate Min Run: The calculateMinRun function determines the size of the runs.
• Sort Runs: The array is divided into runs, and each run is sorted using insertion sort.
• Merge Runs: The sorted runs are merged using the merge function to produce the final sorted array.
• Insertion Sort: The insertionSort function sorts the elements within each run.
• Merge: The merge function merges two sorted subarrays into one sorted subarray.

---

Python Program to Implement Tim Sort

MIN_RUN = 32

def calculate_min_run(n):
    r = 0
    while n >= MIN_RUN:
        r |= n & 1
        n >>= 1
    return n + r


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


def merge(arr, l, m, r):
    len1, len2 = m - l + 1, r - m
    left, right = [], []
    for i in range(0, len1):
        left.append(arr[l + i])
    for i in range(0, len2):
        right.append(arr[m + 1 + i])

    i, j, k = 0, 0, l

    while i < len1 and j < len2:
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    while i < len1:
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len2:
        arr[k] = right[j]
        j += 1
        k += 1


def tim_sort(arr):
    n = len(arr)
    min_run = calculate_min_run(n)

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

    size = min_run
    while size < n:
        for left in range(0, n, 2 * size):
            mid = min(n - 1, left + size - 1)
            right = min((left + 2 * size - 1), (n - 1))
            if mid < right:
                merge(arr, left, mid, right)
        size *= 2


# Example usage:
array = [5, 21, 7, 23, 19, 0, 17, 22, 11, 13]
print("Original array:", array)
tim_sort(array)
print("Sorted array:", array)  # Output: [0, 5, 7, 11, 13, 17, 19, 21, 22, 23]

This Python program defines functions to perform Tim sort on an array. The tim_sort function divides the array into runs, sorts each run using insertion sort, and then merges the sorted runs using merge sort.