best case of quick sort

[tubby123]

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]

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.

[mrnutty]

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