Strand Sort in Python

Question

After reading about Strand Sort on Wikipedia and testing the provided Python version, I decided to try my hand at a faster implementation. I've studied the "Time Complexity" page, read many different approaches to mergesort (and borrowed some), tested the code myself with profiler, line_profiler, and timeit, and I think I've got sped up pretty well.

I'm looking for any ideas on how to optimize this code without changing the sorting algorithm itself or resorting to using Python's timsort for any number of elements.

def strand_sort(array):
    if len(array) < 2:
        return array
    result = []
    while array:
        i = 0
        sublist = []
        sublist.append(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(list(result), sublist)
    return result

def merge(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

Answer 1

• When calling merge(list(result), sublist) it is not necessary to create a copy using list(result), because merge creates a new list.
• You initialize sublist with the last element of array. Popping the last element is most efficient, yes, but it means that sorting an already sorted list is not the best case for you. Instead the best case is a rather rare situation where the list is otherwise sorted exept that the smallest item is at the end.
• Using del array[i] involves moving all subsequent items one position back. You could avoid the use of del by appending to two new lists instead.

Answer 2

You're wasting a bit of time instantiating an empty list to instantly append to it with sublist. You'd be better off creating sublist as a list containing the array.pop() element.

    sublist = [array.pop()]

You could also save time in merge by just calling len once at the start. Since these lists aren't modified in the loop there's no need to call it on each iteration.

Stylewise, you could have better names. I know you can't call it a list, but array isn't quite accurate. Maybe sortable or collection? More importantly, you don't need to use num when your algorithm actually works on characters lexicography.

>>> strand_sort("See this can actually still be sorted".split())
['See', 'actually', 'be', 'can', 'sorted', 'still', 'this']

This obviously causes a little oddness with capitals being sorted before other letters. But since you're just using the > symbol, then this algorithm works on any object that has a function for the operator. I think it's worth noting in a docstring that this can be done, and you can highlight its limitation for sorting strings or explicitly say not to use it for strings even though it's possible.