Sorting through the universe (insertion sort, merge sort and quick sort) 🌈👩🏻‍💻

From Giphy.com

Sorting a list of items into an order that suits your desire is kinda like the sorting hat in Hogwarts trying to find the best house for young witches. 🎩 It’s exciting, but could be a bit tricky to implement in an algorithm — like, how do we make sure that we are using the fastest method to sort, and how much space are we taking up in the memory storage of the sorting engine? We are gonna discuss all of the intricacies of those problems in this article. (Because of the readability of python, I’m using python to show examples of the code.)

Insertion Sort 😐

Insertion Sort is sorting given items by taking an unsorted item, inserting it in sorted order in front of the other items, and repeating until all items are in order.

Rainbow Insertion sort (from Morolin’s sorting algorithms visualized)

def insertion_sort(items):
    for i in range(0, len(items)-1):
        if items[i] > items[i+1]:
            insert_item = items.pop(i)
            last_index = i
            for j in range(last_index-1):
                if items[j] > insert_item:
                    items.insert(j, insert_item)

Since we are only moving the smaller item in front without moving blocks of items, the whole process is relatively stable, and it would be O(n) time in the best case 😃. However, since we are looping through the item, from the last sorted item to the end of the list, the average case running time would be O(n²), which is not ideal at all 😰. Also, since we only rearrange the original array of items, the average memory storage space would only be O(1).

So overall, selection sort would only be great for a nearly sorted list.

Merge Sort 😍👍

Rainbow Merge sort (from Morolin’s sorting algorithms visualized)

Merge sort is a classic divide and conquer algorithm. First, we need a function to divide a list into two equal length lists. Than, we are gonna sort the two lists separately, and finally, we need to have a function to merge the two sorted lists into a new list containing all items in sorted order.

1. divide (this is the main function , we use it to call conquer and merge recursively)

def split_sort_merge(items):
    mid = len(items) // 2
    items1 = items[:mid]
    items2 = items[mid:]
    insertion_sort(items1)
    insertion_sort(items2)
    items[:] = merge(items1, items2)

Here, to reuse code, I’m calling insertion sort that we defined earlier to sort the two separate lists.

2. merge

def merge(items1, items2):
    merged_list = []
    l_index = 0
    r_index = 0
    while l_index < len(items1) and r_index < len(items2):
        if items1[l_index] < items2[r_index]:
            merged_list.append(items1[l_index])
            l_index += 1
        elif items1[l_index] > items2[r_index]:
            merged_list.append(items2[r_index])
            r_index += 1
        else:
            merged_list.append(items2[r_index])
            merged_list.append(items1[l_index])
            r_index += 1
            l_index += 1
    if l_index == len(items1):
        for i in range(l_index):
            merged_list.append(items2[i])
    elif r_index == len(items2):
        for i in range(r_index):
            merged_list.append(items2[i])
    return merged_list

So we are iterating through the two lists and appending whatever is the smaller item to the empty list, after we are done with one list, we just append the items left in the other list to the empty list.

Since we keep dividing lists into two smaller lists at each recursive call, which gives it log(n) component, and at each stage we also compare through the items in the list to decide which one is smaller among the two halves, the average running time is O(n*log(n)) 👏. However, we are making a new list, so the memory storage space is O(n) 😐.

Quick Sort 😂👍😳

Rainbow Quick sort (from Morolin’s sorting algorithms visualized)

Quick sort is an algorithm that chooses a random pivot (in this case we start from the first item) and sorts items smaller than it to the left and items bigger than it to the right till all items are in sorted order.

def quick_sort(items):
    pivot = items[0]
    lesser_list = []
    greater_list = []
    for i in range(1, len(items)):
        item = items[index]
        if item <= pivot:
            lesser_list.append(item)
        else:
            greater_list.append(item)
        quick_sort(lesser_list)
        quick_sort(greater_list)
    items[:] = lesser_list + pivot + greater_list

Since we are dividing an array into two halves in each stage, it has log(n) operation, and each partition loops through the whole array, taking O(n) time — so in total, the average running time is O(n*log(n)).

Although it’s a space sorting algorithm, we are calling each operation recursively, so we have extra stack frames space: log(n), hence, the average space is O(log(n)).

To reduce the risk of an unbalanced pivoting point, which may cause extra running time, I suggest that we choose the pivot to be a random index.

😨☠️ Caution: Since it’s moving blocks of items during each operation, it’s highly unstable 😱, so, keep that in mind if your app requires the stability of data. Also, we should avoid using quick sort if it’s a nearly sorted list, cause it’s gonna loop through the list of items anyways 🤷🏻.‍

Best Practice 😃: Quick sort works really well with a list with only a few unique items, cause it would group similar items together fast and reduce the redundant comparison 🙌.

If you liked this article, click the👏 so more people will see it here on Medium. Thx! ❤️💚💛