For heapsort: if the file is reverse sorted (reversed from the order you want to end up with) then the array already contains an appropriate heap. Thus insertion into the heap is O(n). The extract operation (extract_min or extract_max, depending on order of heap) is stil going to promot the last element to the root of the heap and push it back down to where it belongs. Thus it is an O(lg n) operation performed for each extraction or O(n lg n) for all of them. O(n) + O(n lg n) = O(n lg n).

But wait, is this the very best case? What if the array is monotonic (contains only one value)? Then the heap is already in place as before (O(n) to realize this) _and_ promoting the farthest leaf to the root does not break the heap property so there is nothing to push down in the heap; extract becomes O(1) and is done n times: O(n) for all of the extraction operations: O(n) + O(n) = O(n). The best case is linear in array size. It requires a monotonic array to sort so it is unlikely to be of any real use but this is the best case.

I don't have my algorithm text handy so I can't perform the same analysis for shell sort but if I were to guess where the "best" performance would be I would try a monotonic array.

Hope this helps, -bcl