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.
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.