Worst-case performance of quickSort / getPivot

[Craig Dillabaugh]

On Saturday, 16 November 2013 at 14:20:32 UTC, Jean Christophe
wrote:
clip
>
> 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?
>
> -- JC

This is sort of an interesting problem that you propose, because
while sorting just the pointers means moving things around less,
you would also get absolutely horrible locality of
reference/cache hit performance.

Have you thought about ways to deal with that?