Maxim Neaga
Maxim Neaga

Reputation: 961

Is this Quick sort or Merge sort?

Here is the function:

def sort(unsorted):
    less = []
    equal = []
    greater = []

    if len(unsorted) < 1:
        return unsorted

    pivot = unsorted[-1]

    for element in unsorted:
        if element < pivot:
            less.append(element)
        if element == pivot:
            equal.append(element)
        if element > pivot:
            greater.append(element)

    return sort(less)+equal+sort(greater)


unsorted = [7 ,2, 1, 8, 6, 3, 5, 4]
print sort(unsorted)

I am having hard time defining it as either Quick sort or Merge sort. Conceptually, I think it fits the definition of Quick sort: it uses a pivot to separate elements into smaller and bigger than pivot subsets and then sorts them recursively. But on the other hand it very much reminds me of Merge sort, since it recursively breaks down given list into smaller chunks and them assembles them back together (although around the "pivot").

So is this a Quick sort or Merge sort?

Upvotes: 0

Views: 291

Answers (4)

Jim Mischel
Jim Mischel

Reputation: 133975

This is clearly a quicksort implementation rather than a merge sort. Think of how Quicksort works: it picks a pivot on the full array and rearranges it so that everything left of the pivot value less than the pivot value, and everything to the right is greater than the pivot. So, given the array [7 ,2, 1, 8, 6, 3, 5, 4], and a pivot value of 4, you get [3,2,1,4,8,7,6,5].

Next, it partitions the subarrays to the left and right of the pivot. Let's use 2 for the pivot on the left site, and 6 as the pivot on the right. Doing the left first, we end up with [1,2,3,4,8,7,6,5]. Then the right is partitioned recursively and you end up with [1,2,3,4,5,6,7,8].

Quicksort is top-down. It partitions the entire array, then two subarrays, and recursively partitions each subarray until the length of the subarray is 1.

Merge sort is bottom-up. It starts by making a pass through the array, "merging" adjacent items. So after the first pass, the array is [2 ,7, 1, 8, 3, 6, 4, 5]. Next, it merges adjacent two-element arrays. The first merge is the subarray [2, 7, 1, 8], yielding [1,2,7,8]. The second merge is [3, 6, 4,5], yielding the complete array [1,2,7,8,3,4,5,6].

Finally, it merges the two four-element subarrays, yielding the sorted array.

Your code clearly works top-down: it partitions the initial array, then recursively partitions the left and right subarrays. There is no merging involved, but rather an append step that reassembles the subarrays from the sorted partitions.

Note that people sometimes talk about "top-down" or "bottom-up" merge sort. That has to do more with if the algorithm is written iterative or recursive, not how the actual sorting work is done. Regardless of the implementation, it always starts by merging two one-element subarrays (adjacent items).

Upvotes: 1

user1196549
user1196549

Reputation:

Quicksort partitions, MergeSort merges.

There is clearly a partitioning process (small keys on one side, large keys on the other), and there is clearly no merging (two sorted sequences intertwined in a single one).

Upvotes: 2

MatTheWhale
MatTheWhale

Reputation: 977

A merge sort doesn't need to iterate through the entire array making comparisons before dividing.

Upvotes: 0

Yeongbae
Yeongbae

Reputation: 57

Merge sort always divides the list at index of len(list) / 2. But since this code divides the arr based on the value at list[-1] , this is quick sort

Upvotes: 1

Related Questions