testing code

x.py

import timeit
from random import shuffle, randrange
from functools import partial
from collections import deque
import time


def mean(al):
    return sum(al)/len(al)

def strand_sort_original(array):
    if len(array) < 2:
        return array
    result = []
    while array:
        i = 0
        sublist = [array.pop()]
        while i < len(array):
            num = array[i]
            if num > sublist[-1]:
                sublist.append(num)
                del array[i]
            else:
                i = i + 1
        result = merge_original(result, sublist)
    return result

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

def strand_sort_original_2(array):
    if len(array) < 2:
        return array
    result = []
    while array:
        i = 0
        sublist = [array.pop()]
        while i < len(array):
            num = array[i]
            if num > sublist[-1]:
                sublist.append(num)
                del array[i]
            else:
                i = i + 1
        result = merge_original_2(result, sublist)
    return result

def merge_original_2(l1, l2):
    if not l1: return l2
    if not l2: return l1

    if l1[-1] > l2[-1]:
        l1, l2 = l2, l1

    it = iter(l2)
    y = next(it)
    result = []

    for x in l1:
        while y < x:
            result.append(y)
            y = next(it)
        result.append(x)
    result.append(y)
    result.extend(it)
    return result

def strand_sort_gengisteve(array):
    if len(array) < 2:
        return array
    result = []
    while array:
        sublist = [array.pop()]
        sub_append = sublist.append
        leftovers = []
        left_append = leftovers.append
        for item in array:
            if item > sublist[-1]:
                sub_append(item)
            else:
                left_append(item)
        result = merge_gengisteve(result, sublist)
        array = leftovers
    return result

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

    while array:
        sublist = [array.popleft()]
        last = sublist[0]
        sub_append = sublist.append
        leftovers = deque()
        left_append = leftovers.append
        for item in array:
            if item >= last:
                sub_append(item)
                last = item
            else:
                left_append(item)
        result = merge_deque(result, sublist)
        array = 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(100)],
        [randrange(0, 1000) for _ in range(1000)],
        [randrange(0, 1000) for _ in range(10000)],
        [randrange(0, 1000) for _ in range(100000)],
        ]
def main():
    reps = 2
    num = 2

    tests = [
            'strand_sort_gengisteve_2',
            'strand_sort_original',
            'strand_sort_original_2',
            ]
    print("    Name \t\tMean\t\t\tMin\t\t\tMax")
    for l in range(len(temp)):
        print('---')
        print('on a list of {} items'.format(len(temp[l])))

        for name in tests:

            test = '{}(temp[{}][:])'.format(name,l)
            setup = 'from __main__ import {}, temp'.format(name)
    
            t = timeit.Timer(test, setup)
    
            runs = t.repeat(reps, num)
            print('{}: \t{} {} {}'.format(name,
                    mean(runs),
                    min(runs),
                    max(runs),
                    ))


if __name__ == '__main__':
    main()