1
\$\begingroup\$

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)
\$\endgroup\$
4
  • 1
    \$\begingroup\$From your description, that's not merge sort, it's quicksort.\$\endgroup\$
    – Tom Karzes
    CommentedDec 7, 2017 at 11:30
  • \$\begingroup\$Merge sort combines 2 sorted lists in the end, not 3. This is definitely quicksort instead.\$\endgroup\$
    – RoadRunner
    CommentedDec 7, 2017 at 11:49
  • \$\begingroup\$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.\$\endgroup\$
    – boardrider
    CommentedDec 8, 2017 at 8:20
  • \$\begingroup\$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.\$\endgroup\$
    – marcv81
    CommentedDec 18, 2017 at 9:58

1 Answer 1

Reset to default
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$quicksort is thus essentially recursive, and mergesort essentially iterative.\$\endgroup\$
    – Will Ness
    CommentedDec 19, 2017 at 9:15