quicksort question

[4ET0pfjN]

Hi, I was reading up on quicksort and it said that the pivot is chosen so that hopefully lower sublist and upper sublist are ~ equal size. Why does it matter if it is lopsided or not?

[Cubbi]

The number of operations required to sort the list would be greater. Consider the case when it is *so* lopsided that the pivot is the smallest element of the list, every time.

[4ET0pfjN]

But that has nothing to do with the pivot, it depends on the actual list items.
Eg: let's say original list is: 50, 60, 50, 49, 30, 40, 70, 90

When we write quicksort program, are we supposed to compare all elems to pick a pivot, I'm confused b/c what if all the data are greater than some value as in the above eg with everything greater than 30?

[Cubbi]

If everything is greater than 30 and you picked 30 as pivot, you've picked the worst possible pivot. Hopefully your pivot-choosing algorithm won't pick 40 or 90 on the next iteration.

[Peter87]

Often you just pick a random pivot or the one in the middle.

[Gaminic]

Depending on how large the set is, you can pick three elements and take the middle one. If the set isn't large enough to support the overhead of 3-med, you probably shouldn't be using quicksort in the first place.

[4ET0pfjN]

I want to implement quick sort on my own, and not google the answers, so I learn, but I cannot wrap my head around recursion, I mean when we partition until base case of two elems to sort and return or 1 elem returned, but don't I need multiple arrays at each recursive call?

Another question, is how do I "add" to a lower or upper sublist at each level (at each recursive call)

eg:

if more than 2 elems, then:
determine pivot
if cur item < pivot,
"add" to lower sublist
if cur item >= pivot,
"add" to upper sublist

Because I don't think we are supposed to keep making a new array at each recursive call, right?