Each element can be swapped at most once with each other element. So the number of swaps is less than n choose 2, i.e., quadratic. (This does not mean that th

Each element can be swapped at most once with each other element. So the number of swaps is less than n choose 2, i.e., quadratic. (This does not mean that the run time is quadratic, since pairs can be chosen multiple times, and left alone each time because they are already in order.) EDIT: Whoops, I lied: 3,2,1 -> 2,3,1 -> 1,3,2 -> 1,2,3 2 and 3 switch twice. Anyways, the (whole number) quantity sum_{j=1,...,n}(|x_j - j|) seems to be decreasing under this sort, and it's initial value is O(n squared), so I guess the algorithm should have performance O(n squared), but it will be slower in reality because random choice is not O(1).