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)

• Tom Karzes: From your description, that's not merge sort, it's quicksort.
• RoadRunner: Merge sort combines 2 sorted lists in the end, not 3. This is definitely quicksort instead.
• boardrider: Re "and split the list into three: list of smaller numbers, Equal to and greater than k.": why do you need to sort the list of Equals? By definition, that list is already sorted.
• marcv81: This is neither mergesort nor quicksort. Based on the description of your algorithm, one optimization to shorten the code and simplify the logic would be to only use 2 buckets rather than 3 (e.g.: lower or equal, and higher). The time complexity is O(N log N) which is optimal. The space complexity is also O(N log N): look up quicksort for a similar algorithm in O(N) space.

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.

• Will Ness: quicksort is thus essentially recursive, and mergesort essentially iterative.