3 ms·
and once in a while, the shuffle puts the elements in a pattern that makes quicksort perform worst case (n^2). But i guess that is rare, the larger the list! So
by chii 4y ago
and once in a while, the shuffle puts the elements in a pattern that makes quicksort perform worst case (n^2). But i guess that is rare, the larger the list! So in practice, it works.
- PartiallyTyped 4y agoThe larger the list it gets exponentially less likely that this occurs if the shuffling occurs at every iteration. We have 2/(n!) probability that the shuffle sorts the list either way. The probability that it happens on the second level is 2/((n-1)!). So the probability that it happens twice is 4/(1^2 * 2^2 … (n-1)^2 * n) Which ends up being prod_{i=1} ^N i ^ i It’s so astronomically unlikely, that it just never does.