Scans the input once to identify the longest non-decreasing subsequence already in place, collects all out-of-order "dropped" elements into a separate buffer, sorts that buffer, then merges it back with the in-order portion.
On nearly-sorted data with only k out-of-place elements the sort cost shrinks to O((k+1) log(k+1) + n), the sparser the drops, the faster the algorithm, approaching O(n) as k approaches 0.