Sorting and Efficiency

Today I would like to introduce several sorting method by python language and compare their efficiency by Big O

First one: Insertion Sort

def insertion_sort(sort_list):

     iter_len = len(sort_list)

     if iter_len < 2:

         return sort_list 

    for i in range(1, iter_len):

         key = sort_list[i]

         j = i - 1 

        while j>=0 and sort_list[j]>key:

             sort_list[j+1] = sort_list[j]

             j -= 1 

        sort_list[j+1] = key

    return sort_list 

Insertion sort has two nested loops:

Outer loop runs once for each element in the original unsorted loop

Inner loop runs through sorted list to find the right insertion point

And thus the efficiency is O(n^2)

Second one: Selection Sort

def selection_sort(sort_list):

     iter_len = len(sort_list)

     if iter_len < 2: 

        return sort_list

     for i in range(iter_len-1):

         smallest = sort_list[i]

         location = i 

        for j in range(i, iter_len):

             if sort_list[j] < smallest:

                 smallest = sort_list[j]

                 location = j

         if i != location: 

            sort_list[i], sort_list[location] = sort_list[location], sort_list[i] 

    return sort_list

The basic idea of selection sort is: 

For each element i in the list:

1) „Find the smallest element j in the rest of the list

2) Swap i and j

And thus the efficiency is O(n^2/2)=O(n^2)

Third one: Bubble Sort

def bubble_sort(sort_list):

     iter_len = len(sort_list)

     if iter_len < 2:

         return sort_list

     for i in range(iter_len-1):

         for j in range(iter_len-i-1):

             if sort_list[j] > sort_list[j+1]: 

                sort_list[j], sort_list[j+1] = sort_list[j+1], sort_list[j] 

    return sort_list

The basic idea of bubble sort is:

Run through the array, exchanging values that are out of order

Outer loop can execute a maximum of n-1 times

Inner loop can execute a maximum of n-1 times

And thus the efficiency is O((n-1)^2) = O(n^2)

For now we can see that the three sorting algorithms introduced above all have the same efficiency O(n^2)

So do we have any more efficient algorithm?

And the answer is Yes!

Fourth one: Merge Sort

def merge_sort(sort_list):

    def merge2(L1:list, L2:list) -> list:

        L = []

        L1.reverse()

        L2.reverse()

        while L1 and L2:

            if L1[-1] < L2[-1]:

                L.append(L1.pop())

            else:

                L.append(L2.pop())

        L1.reverse()

        L2.reverse()

        return L + L1 + L2

    if len(sort_list) < 2 :

        return sort_list

    else :

        left_sublist = sort_list[:len(sort_list)//2]

        right_sublist = sort_list[len(sort_list)//2:]

        return merge(merge_sort(left_sublist), merge_sort(right_sublist))

The basic idea of Merge Sort is:

1）Break the data into two equal halves

2）Sort the halves

3）Merge the two sorted lists

And here we sort the halves by recursion

It's easy to find out that the efficiency of step Merge is O(n)

And it's also not difficult to conclude that the number we splits the list is O(logn)

And thus the efficiency of Merge Sort is O(nlogn) < O(n^2)