With the problem as defined, you're right (immediately done). With the problem as "stylistically feels right" - you stop when there are no elements in S that are smaller than the item you just took (so this check happens after replacement), the other approach is appropriate.