Consider repeatedly looping through n+1 objects when only n fit in cache. In that case LRU misses/evicts on every lookup! Your cache is useless and performance falls of a cliff! 2-random turns that performance cliff into a gentle slope with a long tail(?)
I bet this effect happens when people try to be smart and loop through n items, but have too much additional data to fit in registers.
Bubble sort seems pretty terrible, until you realize that it's interruptible. The set is always a little more sorted than before. So if you have realtime requirements and best-effort sorting, you can sort things between renders and live with the possibility of two things relative close to each other appearing a little glitched for a frame.
One iteration of insertion sort will place one additional element in its correct place, but it leaves the unsorted portion basically untouched.
One iteration of bubble sort will place one additional element into the sorted section and along the way do small swaps/corrections. The % of data in the correct location is the same, but the overall "sortedness" of the data is much better.