A reader asked if LINQ's sort has the same vulnerability. I added tests for sorting an array using LINQ's 'orderby' clause. Another reader wondered if the Sort() method for generic lists had the same problem so I added that test as well.
Time required for sorting one million items provided by an adversary:
|Zimbry Introsort||one-half second|
|.Net CLR (Array)||1,588 seconds|
|.Net CLR (LINQ)||1,916 seconds|
|.Net CLR (List)||1,588 seconds|
Detailed benchmark results are here: Sorting up to 1 million items (with an adversary)
Notes on the test:
All tests were run under .Net framework version 4.0
The times reported in the table are an average of the times taken for one ascending sort and one descending sort.