Algorithms with Python - Merge Sort and Tim Sort

10 minute read


Continuing on our journey to explore sorting algorithms with Python, we will talk about the following in our Part 2 of the Sorting Algorithms w/ Python series.

  • Merge Sort
  • Tim Sort

Array Sorting Complexities

Recall the time complexities (for a full summary, see Part 1).

Algorithm   Time Complexity  
  Best Average Worst
Merge Sort Ω(nlog(n)) θ(nlog(n)) O(nlog(n))
Tim Sort Ω(n) θ(nlog(n)) O(nlog(n))

Note that compared to the algorithms we’ve talked about in Part 1, these algorithms has better time complexity properties. We will explain how that is achieved.

Sorting Algorithms

Merge Sort

(gif Credit)

Merge sort is a classic “divide and conquer” algorithm, where we split up the list that needs to be sorted, sort them in small batches, then put them back together in order. In particular, the first step is to divide all elements into single elements, then combine into pairs, sort the pair, then combine into 4-element batches, and so on, until we have a sorted list.

Python Implementation

# merge sort
def merge_sort(to_sort):
    Given a list of integers,
    sorts it into ascending order with Merge Sort
    (in place)
    and returns the sorted list
    # length of array to sort
    list_len = len(to_sort)
    if list_len > 1:
        mid = list_len // 2
        L = to_sort[:mid]
        R = to_sort[mid:]

        # here we recursively incur the mergesort function
        # The effect is that it will first divide up the
        # entire list into individual bits.
        # Notice that merge_sort(single element) does nothing
        # so that when we reach merge_sort of 2 elements
        # we can finally go beyond this point

        # Once all elements are divided through the recursive calls
        # The function call can finally reach these later codes

        # i: index of element we are looking at in list L
        # j: index of element we are looking at in list R
        # k: total comparisons made / elements saved into arr
        i = j = k = 0

        # now we look at each list L and R
        # starting from the smaller elements (left)
        while i < len(L) and j < len(R):
            # if element from L is smaller than
            # element from R, we pop off the element from L
            # save it to our array
            # and move on to the next element in L
            if L[i] < R[j]:
                to_sort[k] = L[i]
                i += 1
            # similarly the case if the element in R is larger
                to_sort[k] = R[j]
                j += 1

            k += 1

        # Checking if any element was left
        # when one of the list L or R has been exhausted
        # If so, all elements left are larger than the rest.

        # if i < len(L): R is exhausted.
        # save all remaining elements from L into arr
        while i < len(L):
            to_sort[k] = L[i]
            i += 1
            k += 1

        # similarly the opposite case
        while j < len(R):
            to_sort[k] = R[j]
            j += 1
            k += 1

    return to_sort

Now let’s test the code:

# generate some random integers
import random
to_sort = random.sample(range(1, 1000), 20)

# [61, 309, 414, 688, 123, 669, 473, 845, 330, 231, 173, 758, 797, 374, 511, 20, 28, 958, 196, 25]

# [20, 25, 28, 61, 123, 173, 196, 231, 309, 330, 374, 414, 473, 511, 669, 688, 758, 797, 845, 958]

Time Complexity

Regardless of the initial condition of the list, Merge Sort always divide and conquers. Within each level of division, the number of comparisons required is on the order of n (n/2 for last level, n/2 to 3n/4 for second to last level, etc.), and the number of levels are of order log(n), since 2# of levels is on the order of n. To show how stark the difference this is from the quadratic time complexities, the # of comparisons is plotted below for merge sort and insertion sort:


As we can see, as the length of the list increases, the big-O difference really starts to reveal itself, where the # of comparisons required for insertion sort simply takes off.

Tim Sort

Tim sort was created in 2001 for implementations of sorting functionalities in Python. It is real-world focused, takes advantage of the superior performance of insertion sort on smaller lists in real-world data where consecutive ordered elements are often present, and the ability of merge sort to combine sorted sub-lists into one final sorted list. The actual implementation has more details, but the implementation below should give us a feel of the inner workings.

Python Implementation

# tim sort
# Adapted from

# custom binary search
def binary_search(arr, item, start, end):
    This is a recursive implementation of
    searching for the correct position of an `item`
    in a sorted array `arr`
    using binary search technique.

    The item may or may not be present in arr.

    start / end are specified for recursive calls.

    Initial call would specify them as start / end of
    arr, respectively. i.e.
    start = 0
    end = len(arr) - 1

    # first specify end game
    # if the two pointers meet,
    # it means we are done searching.
    # and we need to determine the final index
    if start == end:
        if arr[start] > item:
            # item should be inserted to the left of start
            return start
            # item should be inserted to the right of start
            return start + 1
    # if we arrive at this state without finding the location
    # ((start + end) // 2 is within 1 of end)
    # and start != end --> start == end - 1
    # it means that start is the correct location
    if start > end:
        return start

    mid = (start + end) // 2
    # if item is larger, search in upper half
    if arr[mid] < item:
        return binary_search(arr, item, mid + 1, end)
    # else, search in lower half
    elif arr[mid] > item:
        return binary_search(arr, item, start, mid - 1)
        return mid

# insertion part
def insertion_sort(to_sort):
    Given a list of integers,
    sorts it into ascending order with Insertion Sort
    (done in place)
    and returns the sorted list
    # length of array to sort
    list_len = len(to_sort)
    # for each pass, the elements to its left
    # is already sorted, and we need to insert
    # element i into the correct location
    for i in range(1, list_len):
        # element in question
        el = to_sort[i]
        # keep track of where to insert el
        shift_count = 0
        # start comparing from right to left
        # so that we can easily replace in place
        for j in range(i-1, -1, -1):
            if to_sort[j] > el:
                # for all elements larger than el
                # shift it 1 index to the right
                to_sort[j+1] = to_sort[j]
                # el needs to shift 1 more unit to the left
                shift_count += 1
                # once we hit an element not larger than el
                # we can terminate the process, since the rest
                # is all going to be smaller
        # insert el
        to_sort[i-shift_count] = el

    return to_sort

def merge(left, right):
    Takes two sorted lists and returns a single sorted list by comparing the
    elements one at a time.

    For detailed explanation of the logic, see Part 1
    where merge_sort is explained and implemented
    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:])

# putting together
def timsort(to_sort):
    # timsort uses a concept called "runs"
    # where consecutive elements in order will be
    # put into a run and merged together.
    # The actual timsort is more advacned in constructing the
    # runs, but the code below suffices to illustrate the logic.
    runs, sorted_runs = [], []
    l = len(to_sort)
    new_run = [to_sort[0]]
    for i in range(1, l):
        # if last element
        if i == l-1:
            # append to new run, and add new run to all runs
        # if next element is larger then current
        # i.e. is not in order
        if to_sort[i] < to_sort[i-1]:
            # if current run is empty
            if not new_run:
                # append a singleton list to the runs
                # and append next element to new run
            # if we have a non-empty run
                # append the run to the list of runs
                # start new empty run
                new_run = []
        # if in order, just add next element to current run

    # Note that our implementation of the "runs"
    # actually results in already sorted runs
    # such that this insertion_sort step is redeundant.
    # However, in a more sophisticated setup, the "runs"
    # would not be completey sorted, but would comtain
    # some bits of unsorted data, and truncated to make sure
    # each run is of specified length (or shorter),
    # where insertion sort performs best
    for each in runs:
        # use insertion sort to sort each run,
        # and append to sorted_runs to keep track
    sorted_array = []
    for run in sorted_runs:
        # finally, for each of these sorted runs
        # we merge them together
        sorted_array = merge(sorted_array, run)
    return sorted_array

Time Complexity

In best case scenario, where the list is already sorted, the run-construction, insertion sort, and merging part each takes linear time. Hence a big-) of n. Average case and worst case is bounded by merge sort’s nlog(n) complexity.


Leave a comment