Trace nums = [1, 5, 8, 4, 7, 6, 5, 3, 1].
Scan right to left for a pivot (element smaller than its right neighbor). Index has value , not a pivot. Index has value . Pivot found at index .
Suffix from index : [7, 6, 5, 3, 1] (descending). Find the smallest value greater than : that's at index .
Swap: [1, 5, 8, 5, 7, 6, 4, 3, 1]. Reverse suffix from index : [1, 5, 8, 5, 1, 3, 4, 6, 7].
You scan the array at most twice (find pivot, find swap target) and reverse a suffix. All operations are time. Everything is in-place: space.