## tubby123 -4

can u give me an example array of the best case of quick sort?
I do understand that the best case of quick sort is when the elements are already in the pivot place., and that the complexity is O(n logn), but i m just not able to come up with a large array, that fits this condition perfectly.

## Narue 5,707

The best cast for quicksort is an already sorted array when the implementation checks for an already sorted subset. In such a case, no partitioning takes place and no recursive calls are made, which results in linear complexity:

``````function quicksort(a, first, last)
if is_sorted(a, first, last) then
return
end if

pivot := partition(a, first, last)

quicksort(a, first, pivot - 1)
quicksort(a, pivot + 1, last)
end function``````

Assuming the original quicksort algorithm with no improvements, the best case is an even partitioning in all steps, which is O(N log N).

i m just not able to come up with a large array, that fits this condition perfectly

The dependency is your partitioning scheme, so to create an array that fits the best case, you need both a deterministic partitioning scheme (ie. random pivots will need to be mocked) and an array that gets partitioned perfectly each time. Without knowing your partitioning algorithm, I can't really offer much more advice than that.

commented: And that about covers it... +11

## firstPerson 761

Hint: Use your pivot algorithm to work from the bottom up instead of top down