Break the inner loop into three parts, j < i, j == i, j > i, and you can see it's insertion sort with extra steps. for i = 1 to n do - Inserts A[i] into

Break the inner loop into three parts, j < i, j == i, j > i, and you can see it's insertion sort with extra steps. for i = 1 to n do - Inserts A[i] into A[1 to i-1], using the A[i] - spot as a temp variable. for j = 1 to i-1 do if A[i] < A[j] then swap A[i] and A[j] - Does nothing. for j = i do if A[i] < A[j] then swap A[i] and A[j] - Permutes A[i to n], placing the maximum into - A[i]. Since A[i] already has the max after the - first iteration, it won't change, and we don't - care how A[i+1 to n] is permuted since it gets - sorted anyway. for j = i+1 to n do if A[i] < A[j] then swap A[i] and A[j]