News for hackers. Stuff that matters.
Re:Changing std:sort at Google’s scale and beyond by jmalicki on Wednesday April 20, 2022 @01:38PM (#31100334)
If you examine the modification more closely, it is just finding the list that would exhibit worst case performance - once created, that list would always exhibit the worst case as a constant list.

Once you have the resulting list, the indices are sorted, then assigning each num_solid value to that index would result in the list being constant, and then could be sorted to give such worst case behavior.

I wish the article was more clear on this.

There are no comments on this comment yet.