Here's one way to intuitively think about this algorithm: ICan’tBelieveItCanSort(A[1..n]) for i = 1 to n do for j = 1 to n do if A[

Here's one way to intuitively think about this algorithm: ICan’tBelieveItCanSort(A[1..n]) for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] and A[j] Example: 3412 // i=1 4312 // i=1 -> i=2 3412 // i=2 -> i=3 1432 // i=3 1342 // i=3 -> i=4 1243 // i=4 1234 // i=4 1) After an outer loop of i is finished, the first i elements are in ascending order. (For example, in the fifth line above after i=3 is finished, the first 3 elements are "124") 2) At some point, the outer loop will point to "1", and "1" will be compared to the 1st position. Then, "1" will be placed in the 1st position and remain there forever. (For example, this happens in the 3rd line above) 3) After the outer loop points to "1", at some point it will point to "2" which will be compared to the 2nd position. (Proof: when the outer loop pointed to "1", if "2" was on the right of "1", then the statement is obvious; if "2" was on the left of "1", then it would be in the 1st position by (1), so again the statement holds.) Then, "2" will be placed in the 2nd position and remain there forever. 4) After the outer loop points to "2", at some point it will point to "3" which will be compared to the 3rd position...