Insertion Sort

Algotihm works next way. We walk throught array and picks elements one-by-one from second to last. Then, we find place to insert picked element in the prev part of array and insert it.



In [10]:

    
from functools import partial


def ins_sort(xs, rev=False):
    xs = xs[:]
    comp = (lambda k, t: t < k) if rev else (lambda k, t: t > k)
    for j in range(1, len(xs)):
        i = j - 1
        k = xs[j]
        comp_foo = partial(comp, k)
        while i >= 0 and comp_foo(xs[i]):
            xs[i+1] = xs[i]
            i -= 1
        xs[i+1] = k
    return xs

Insertion sort testing

For testing I'll use built in Jupyter function %timeit.



In [11]:

    
import numpy as np
from functools import partial
from operator import mul

a = list(map(partial(mul, 10), np.random.rand(10000)))
%timeit ins_sort(a)
%timeit ins_sort(a, True)









    



1 loop, best of 3: 14.6 s per loop
1 loop, best of 3: 14.9 s per loop

Merge sort

This sorting algorithm execute in next way.

We split array to two arrays
Sort each of this arrays.
Merge sorted arrays together

merge function

First of all we need to implement merge function. For this function I implement next algorithm.

input: xs, ys - arrays, cf - comparing function (a, a) -> bool

output: zs - merged array

move elements from xs to zs while cf(current xs, current ys) is True or ys is empty
move elements from ys to zs while cf(current ys, current xs) is True or xs is empty
if xs not empty go to 1
if ys not empty go to 2



In [5]:

    
def merge(xs, ys, cf=lambda a, b: b if a > b else a):
    zs = []
    xl, yl = len(xs), len(ys)
    zl = xl + yl
    xi = yi = 0
    for _ in range(zl):
        if xi == xl:
            while yi < yl:
                zs.append(ys[yi])
                yi += 1
            break
        elif yi == yl:
            while xi < xl:
                zs.append(xs[xi])
                xi += 1
            break
        zs.append(cf(xs[xi], ys[yi]))
        if xs[xi] < ys[yi]:
            xi += 1
        else:
            yi += 1
    return zs

Now lets write classic recursive merge sort.



In [6]:

    
def classic_merge_sort(xs):
    if len(xs) < 2:
        return xs
    q = len(xs) // 2
    ys = classic_merge_sort(xs[:q])
    zs = classic_merge_sort(xs[q:])
    return merge(ys, zs)



In [9]:

    
import numpy as np
from functools import partial
from operator import mul

a = list(map(partial(mul, 10), np.random.rand(10000)))
%timeit classic_merge_sort(a)









    



100 loops, best of 3: 8.91 ms per loop

So, merge sort is notably faster than insertion sort, but in python recursion is not best solution.