Recursive quicksort in Python

Question

I want to find a more elegant way to build a recursive sorting function.

The function randomly selects one of the numbers from a given list, k, and splits the list into three: list of smaller numbers, equal to and greater than k.

Now, I recursively sort each list and then combine the 3 to a single sorted list.

For example:

The list [5,2,7,4,9,3] for k = 5 is split into three: [7,9], [5], [2,4,3].

Now sort recursively to get the lists [7,9] and [2,4,3] in order to receive [7,9] and [2,3,4].

The three lists sorted for the receipt of one sorted list: [2,3,4,5,7,9]

Any suggestions?

def partition(lst,k):
    bigger = []
    smaller = []
    equal = []
    i =  0
    while i < len(lst) :
        if lst[i] < k:
            smaller.append(lst[i])
            i += 1
        elif lst[i] == k:
            equal.append(lst[i])
            i += 1
        else:
            bigger.append(lst[i])
            i += 1
    # merge 3 list:
    merged = [smaller,equal ,bigger]
    return merged

def my_sort(lst):
    import random
    k = (random.choice(lst))
    lst3 = partition(lst,k)

    def merge(left, right):
        merged = []

        left_i, right_i = 0, 0
        while left_i < len(left) and right_i < len(right):
            if left[left_i] <= right[right_i]:
                merged.append(left[left_i])
                left_i += 1
            else:
                merged.append(right[right_i])
                right_i += 1
        # copy remaining:
        merged += left[left_i:] + right[right_i:]
        return merged

    def mergesort(lst):
        if len(lst) <= 1:
            return lst

        middle = len(lst) / 2
        left = mergesort(lst[: middle])
        right = mergesort(lst[middle:])
        return merge(left, right)

    left = mergesort(lst3[0])
    right = mergesort(lst3[2])

    print k
    return merge(merge(left,lst3[1]),right)

Answer 1

When you've split a list into a smaller and a bigger halves, after sorting them the elements in the first half are all still smaller than all the elements in the second.

So, merging such sorted halves is just positional concatenation, i.e. putting the two halves beside each other so that in the resulting sequence, first go the elements of the first half (sorted), and then the second.

There's no need to compare the elements values in your merge, results of such comparisons are known in advance, predetermined by the partition stage.

This is the essence of quicksort - partition by value, necessarily putting some effort into doing that, and then, after sorting the halves, join positionally, easily and simply.

The merge sort works the other way - it partitions the list simply, by position; and spends more effort merging the sorted parts, according to the elements' values:

                 mergesort             quicksort

partition        positional            by value

merge            by value              positional

Splitting into three parts is a good optimization, but changes nothing regarding the above.