Strand Sort in Python 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) &lt; 2:
        return array
    result = []
    while array:
        i = 0
        sublist = []
        sublist.append(array.pop())
        while i &lt; len(array):
            num = array[i]
            if num &gt; 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 &lt; len(list_1) and j &lt; len(list_2):
        if list_1[i] &gt; 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
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.

&gt;&gt;&gt; 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 &gt; 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.