Worst-case performance of quickSort / getPivot

[Andrei Alexandrescu]

On 11/17/13 1:23 PM, Chris Cain wrote:
> On Sunday, 17 November 2013 at 16:57:19 UTC, Andrei Alexandrescu wrote:
>> Then, people may want to sort records by e.g. Lastname, Firstname, or
>> index a text by words. For names we'd need some census data or phonebook.
>
> Sure.
>
> As a source of data, app_c.csv from
> http://www.census.gov/genealogy/www/data/2000surnames/ -> File B:
> Surnames...
[snip]

> It needs a bit of work to make it actually generic, but it's a good
> start and I'll just say it's WTFPL code, so use it for whatever. It'll
> be especially good for generating test cases like I have done above.
>
> FWIW, FastDice takes ~400ms to generate all those dice throws. I did a
> back-of-the-envelope calculation on using dice, and just the time saved
> caching the sum saved maybe 30 minutes (No, I didn't wait that long, I
> stopped after 5 and wrote FastDice) of time each run. And the time saved
> using a gallop search instead of linear search is pretty significant as
> well (difference between n and log n time).

I think that's a terrific start! (Not sure I understand where the 30 
minutes come from...)


Andrei