Python 3 Median-of-3 Quicksort Implementation Which Switches To Heapsort After A Recursion Depth Limit Is Met

Functions called: (regardless of class) def partition( pivot, lst ): less, same, more = list(), list(), list() for val in lst: if val < pivot: less.a

Solution 1:

Without seeing your test data, we're flying blind here. In general,

less, same, more = qsPivotMedian3.partition(pivot, lst)

is fine on its own, but you never check less or more to see whether they're empty. Even if they are empty, they're passed on via:

    return quicheSortRec(less,limit-1) + same + quicheSortRec(more,limit-1)

and quicheSortRec() doesn't check to see whether they're empty either: it unconditionally calls:

pivot=qsPivotMedian3.medianOf3(lst)  

and that function will raise the error you're seeing if it's passed an empty list. Note that your quicheSort()does check for an empty input. The recursive worker function should too.

BTW, consider this rewrite of medianOf3():

defmedianOf3(lst):
    returnsorted([lst[0], lst[len(lst)//2], lst[-1]])[1]

This is one case where brevity is clearer ;-)