Pitch [stdlib]: making sorting algorithm selectable

Evolution Pitches
,
61

I meant something like this response:

62

Having gone through this pitch, I would like to bump it saying that just having the option to provide a custom sorting algorithmn is a good one. Let the onus of providing the actual sorting algorithmn be up to the user but the interface & the building blocks be included in the standard library itself.

Intuitive Example:

[5,4,10,1,6,2].sorted(using: BubbleSort(), by: >)

The usage of providing custom sort algorithmns indeed may be rare but the standard library would atleast have that flexibility out-of-the-box.
The above style would be similar to Combine's .decode(type:decoder:) operator that accepts a TopLevelDecoder to do the real decoding:

.decode(Model.self, JSONDecoder())

One might argue but it's also rare that someone will implement their own TopLevelDecoder. Yet... that flexibility is available to us all.

Implementation:

protocol Sorter {
    typealias OrderingHandler<Element> = (Element, Element) throws -> Bool
    func sort<Element>(_ array: inout [Element], by areInIncreasingOrder: OrderingHandler<Element>) rethrows
}

extension Array {
    mutating func sort(using sorter: Sorter, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
        try sorter.sort(&self, by: areInIncreasingOrder)
    }
    
    func sorted(using sorter: Sorter, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element] {
        var array = self
        try array.sort(using: sorter, by: areInIncreasingOrder)
        return array
    }
}

Usage:

class BubbleSort: Sorter {
    func sort<Element>(_ array: inout [Element], by areInIncreasingOrder: OrderingHandler<Element>) rethrows {
        print("Bubble Sort")
    }
}

class InsertionSort: Sorter {
    func sort<Element>(_ array: inout [Element], by areInIncreasingOrder: OrderingHandler<Element>) rethrows {
        print("Insertion Sort")
    }
}

//Sort Approach
var array = [5,4,10,1,6,2]
array.sort(using: BubbleSort(), by: >)

//Sorted Approach
[5,4,10,1,6,2].sorted(using: InsertionSort(), by: >)
63

Thanks for writing this pitch! This feature is needed a lot for Server Side Swift.

Can somebody tell, if standard library do some heuristics to choose best algorithm, depending on elements count for example?
Sorting 10_000, 1_000_000, and 100_000_000 of elements needs different algorithms.

64

How about telling the stdlib what properties you need, and stdlib choosing the fastest implementation for you?

array.sort(properties: [.stable, .inPlace])

Some combinations would be impossible, but that could be checked if/when we have static assertions Compile-Time Constant Expressions for Swift

If having support on stdlib level, what @cukr suggests above seems like the only reasonable exposure of interface IMHO. As previously mentioned, it seems like a bad idea to commit to exposing specific algorithms. If specifying sort algo properties, it allows for the implementation to change (for the better :-) over time.

1 Like