It's a good idea to check if the worst case can happen; at the least such a check gives you an idea about estimate quality. For swap sort the worst case occurs when the input data is sorted in opposite order from what the sort establishes; for example, sorting an array of descending-ordered data to put it in ascending order.
Data in descending order has the property that element i is at least as large as any element j, i < j. For swap sort, this means the if statement guard is always true and a swap is always done. After the inner loop makes one pass through the array (from element i to the end), the elements following i are still in descending order, which means the next time the inner loop is executed, the if guard will still always be true. Swap sort can actually perform O(n2) element movements in the worst case.
This page last modified on 24 January 2006.