Python: Sort unsorted numbers using Timsort

Python Search and Sorting : Exercise-25 with Solution

Write a Python program to sort unsorted numbers using Timsort.

From Wikipedia:
Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3.

Sample Solution:

Python Code:

#Ref:https://bit.ly/3qNYxh9
def binary_search(lst, item, start, end):
    if start == end:
        return start if lst[start] > item else start + 1
    if start > end:
        return start

    mid = (start + end) // 2
    if lst[mid] < item:
        return binary_search(lst, item, mid + 1, end)
    elif lst[mid] > item:
        return binary_search(lst, item, start, mid - 1)
    else:
        return mid
def insertion_sort(lst):
    length = len(lst)
    for index in range(1, length):
        value = lst[index]
        pos = binary_search(lst, value, 0, index - 1)
        lst = lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]
    return lst
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 tim_sort(lst):
    length = len(lst)
    runs, sorted_runs = [], []
    new_run = [lst[0]]
    sorted_array = []
    i = 1
    while i < length:
        if lst[i] < lst[i - 1]:
            runs.append(new_run)
            new_run = [lst[i]]
        else:
            new_run.append(lst[i])
        i += 1
    runs.append(new_run)
    for run in runs:
        sorted_runs.append(insertion_sort(run))
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)
    return sorted_array
lst = [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
print("\nOriginal list:")
print(lst)
print("After applying Timsort the said list becomes:")
sorted_lst = tim_sort(lst)
print(sorted_lst)
lst =  "Python"
print("\nOriginal list:")
print(lst)
print("After applying Timsort the said list becomes:")
sorted_lst = tim_sort(lst)
print(sorted_lst)
lst = (1.1, 1, 0, -1, -1.1)
print("\nOriginal list:")
print(lst)
print("After applying Timsort the said list becomes:")
sorted_lst = tim_sort(lst)
print(sorted_lst)

Sample Output:

Original list:
[5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
After applying Timsort the said list becomes:
[-18, -4, 0, 3, 5, 5, 7, 9, 10, 46, 92, 178]

Original list:
Python
After applying Timsort the said list becomes:
['P', 'h', 'n', 'o', 't', 'y']

Original list:
(1.1, 1, 0, -1, -1.1)
After applying Timsort the said list becomes:
[-1.1, -1, 0, 1, 1.1]

Flowchart:

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to sort a list of elements using Tree sort.
Next: Write a Python program to sort unsorted numbers using Strand sort.