Worst-case performance of quickSort / getPivot

[Jean Christophe]

>> BTW I'm very interested in finding a library which could 
>> Quicksort an array of pointers, where each pointer points to a 
>> class object (or a structure) address. The library would make 
>> possible, for example, to sort the `class objects` using one 
>> of their members as the key. Because the swaps are done on the 
>> actual pointers (and not the Objects pointed), the Quicksort 
>> should be very efficient. However, the algorithm woulnd't be 
>> so trivial to implement because each comparison shall be done 
>> using the Object's member's value :
>>
>> eg. Obj1.foo < Obj2.foo.
>>
>> Of course, the programmer can choose any relevant member 
>> property to sort the collection. And it should be as easy to 
>> use as:
>>
>> class SomeClass { string foo; double bar;}
>> SomeClass[] a;
>> // put 100 000 objects into a
>> a.sort("foo");
>>
>> Do we already have something like that available somewhere or 
>> is it possible to make one eventually?
>
> You mean, sort!`a.foo < b.foo` ?

Yes.

An indirect sorting, assuming a and b to be ojects of class 
SomePotentialyLargeClass.

Because the array to sort contains pointers only, all the data 
movement is essentially the same as if we were sorting integer.

-- JC