Testing the speed of various implementations of Strand Sort

strand_sort_variations.py

import timeit
from random import shuffle, randrange
from statistics import mean
from functools import partial
from collections import deque

def merge_original_1(left, right):
    i = 0
    j = 0
    merged_list = []
    while i < len(left) and j < len(right):
        if left[i] > right[j]:
            merged_list.append(right[j])
            j += 1
        else:
            merged_list.append(left[i])
            i += 1
    merged_list += left[i:]
    merged_list += right[j:]
    return merged_list

def strand_sort_original_3(unsorted):
    if len(unsorted) < 2:
        return unsorted
    result = []
    while unsorted:
        sublist = [unsorted.pop()]
        leftovers = []
        last = sublist[-1]
        for item in unsorted:
            if item >= last:
                sublist.append(item)
                last = item
            else:
                leftovers.append(item)
        result = merge_original_1(result, sublist)
        unsorted = leftovers
    return result

def strand_sort_original_4(unsorted):
    if len(unsorted) < 2:
        return unsorted
    result = []
    while unsorted:
        sublist = [unsorted.pop(0)]
        leftovers = []
        last = sublist[0]
        sublist_append = sublist.append
        leftovers_append = leftovers.append
        for item in unsorted:
            if item >= last:
                sublist_append(item)
                last = item
            else:
                leftovers_append(item)
        result = merge_original_1(result, sublist)
        unsorted = leftovers
    return result

def strand_sort_gengisteve_2(unsorted):
    if len(unsorted) < 2:
        return unsorted
    result = []
    while unsorted:
        sublist = [unsorted.pop()]
        last = sublist[0]
        sub_append = sublist.append
        leftovers = deque()
        left_append = leftovers.append
        for item in unsorted:
            if item >= last:
                sub_append(item)
                last = item
            else:
                left_append(item)
        result = merge_gengisteve(result, sublist)
        unsorted = leftovers
    return result

def merge_gengisteve(left, right):
    merged_list = []
    merged_list_append = merged_list.append

    it_left = iter(left)
    it_right = iter(right)

    left = next(it_left, None)
    right = next(it_right, None)

    while left is not None and right is not None:
        if left > right:
            merged_list_append(right)
            right = next(it_right, None)
        else:
            merged_list_append(left)
            left = next(it_left, None)

    if left:
        merged_list_append(left)
        merged_list.extend(i for i in it_left)
    else:
        merged_list_append(right)
        merged_list.extend(i for i in it_right)

    return merged_list

def strand_sort_deque(unsorted):
    if len(unsorted) < 2:
        return unsorted
    result = []

    while unsorted:
        sublist = [unsorted.popleft()]
        last = sublist[0]
        sub_append = sublist.append
        leftovers = deque()
        left_append = leftovers.append
        for item in unsorted:
            if item >= last:
                sub_append(item)
                last = item
            else:
                left_append(item)
        result = merge_deque(result, sublist)
        unsorted = leftovers
    return result

def merge_deque(left, right):
    merged_list = []
    merged_list_append = merged_list.append

    it_left = iter(left)
    it_right = iter(right)

    left = next(it_left, None)
    right = next(it_right, None)

    while left is not None and right is not None:
        if left > right:
            merged_list_append(right)
            right = next(it_right, None)
        else:
            merged_list_append(left)
            left = next(it_left, None)

    if left:
        merged_list_append(left)
        merged_list.extend(i for i in it_left)
    else:
        merged_list_append(right)
        merged_list.extend(i for i in it_right)

    return merged_list


temp = [
        [randrange(0, 1000) for _ in range(10)],
        [randrange(0, 1000) for _ in range(100)],
        [randrange(0, 1000) for _ in range(1000)],
        [randrange(0, 1000) for _ in range(10000)],
        [randrange(0, 1000) for _ in range(100000)],
        ]

t = temp[4][:]
temp2 = [
        sorted(t)[:],
        [x for x in sorted(t)[::-1]][:],
        t[:],
        ]

def main():
    reps = 2
    num = 2

    tests = [
            'strand_sort_original_3',
            'strand_sort_original_4',
            'strand_sort_deque',
            'strand_sort_gengisteve_2',
            ]

    ls_words = {
            0: "already sorted",
            1: "reverse sorted",
            2: "random order"
            }

    for l in range(len(temp2)):

        print("\n    On a list of {} {} items:\tMean\t\t\tMin\t\t\tMax".format(len(temp2[l]), ls_words[l]))

        for name in tests:

            if name == 'strand_sort_deque':
                test = '{}(deque(temp2[{}][:]))'.format(name, l)
            else:
                test = '{}(temp2[{}][:])'.format(name, l)
            setup = 'from __main__ import {}, temp2; from collections import deque'.format(name)

            t = timeit.Timer(test, setup)

            runs = t.repeat(reps, num)
            print('    {}: {}{}\t{}\t{}'.format(
                    name,
                    '\t\t' if name == 'strand_sort_deque' else '\t',
                    mean(runs),
                    min(runs),
                    max(runs),
                    ))

if __name__ == '__main__':
    main()