CODEWITHSUNDEEP
algorithmsortingbig-oquicksortmergesort
Dinoman979
Dinoman979

Reputation: 27

Understanding running time for merge sort and quick sort

For both merge sort and quick sort, I'm trying to come up with scenarios where they become worst case. If I'm correct, merge sort's worst case O(nlogn) when everything is sorted. Quick sort's worst case is when the pivot is in the least optimal place, and the array is sorted, so it becomes O(n^2). I was wondering if this was correct first off, so please correct me if not. My real question is if the pivot for quick sort is in the middle of an array, what would the array have to look like in order for it to be O(n^2)?

Upvotes: 2

Views: 361

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58271

You can emulate quicksort, making sure that each time the pivot is chosen it's consecutively 0, 1, 2, ... to guarantee worst-case performance.

This assumes a usual pivoting algorithm that will swap the pivot value to the start of the array before partitioning the array in place. In this case, since we're picking the pivot to be the smallest remaining item, there'll be no partitioning to do.

Here's the emulation code:

class Cell:
    def set(self, v):
        self.v = v

def worst_case_quicksort(xs, i):
    xs = xs[:]
    for i in xrange(len(xs)):
        p = (len(xs) - i) // 2
        xs[i+p].set(i)
        xs[i], xs[i+p] = xs[i+p], xs[i]

xs = [Cell() for _ in xrange(20)]
worst_case_quicksort(xs, 0)
print [x.v for x in xs]

The output looks like this:

[1, 11, 3, 19, 5, 13, 7, 17, 9, 15, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

Upvotes: 0

rcgldr
rcgldr

Reputation: 28826

Worst case for quick sort is when the pivot is less than or greater than all of the other values left to be sorted. In this case only 1 item is removed from the remaining values at each level of recursion, and the time complexity ends up O(n^2).

For a basic merge sort, top down or bottom up, the number of moves is always the same. The number of compares depends on the data pattern. When merging two runs of size n each, the worst case number of compares is 2n-1 (when every element but 1 from the two runs is compared, when there's just 1 element remaining, there's nothing to compare to, so it's just copied), the best case is when all of the elements of one run are less than the first element of the other run, in which case the number of compares is n, such as when the data is already sorted or reverse sorted.

Upvotes: 1

Related Questions