Partial sorting?

[nnnnnnnn (Nate Cook)]

Thanks for bringing these up, @CTMacUser — we probably will eventually want both of the C++ algorithms in the standard library. Partial sorting is more efficient than sorting a whole collection if you only need the smallest n of your elements.

I'm not sure I understand what your leastOrderedIndex and mostOrderedIndex do — are they examining the "skipped" elements at all?

@CTMacUser

Can any of these be implemented stably?

There are two kinds of stability for partial_sort, right? Stability of the sorted section at the front and the stability of the unsorted section at the end. The C++ versions aren't stable for either. This would be a question we'd definitely need to discuss when designing this feature in the stdlib.

@Dante-Broggi

You actually can do the transform in place:

var thing = [3, 2, 4, -1, -4]
thing[..<3].sort()
print(thing) // prints [2, 3, 4, -1, -4]

Note that a partial sort isn't the same as sorting part of a collection — the result would be more like:

var thing = [3, 2, 4, -1, -4]
thing.partialSort(upTo: 3)
// [-4, -1, 2, 3, 4]