It's well known that currently, it is possible to sort a collection by using the sort(ed)
function(s).
It's currently unclear without peeking under the hood of swift implementation is the algorithm used for sorting, changes to this algorithm (recently it passed from introsort
to timsort
) and performances tradeoffs.
Different sorting algorithms might be preferred depending on the problem that needs to be solved. In certain cases it's important to know that the sorting is stable, in other cases might be important to be sure that the algorithm is in place.
With the change from swift 4 to swift 5, the sorting algorithm changed from being in place (introsort) to be stable (timsort) with undocumented time complexity (you can find it out just by looking at the swift source code)
Developers choices in sorting their collections might be affected from their current knowledge of the current implementation of the swift sorting algorithm. A change in this implementation might result in breaking backward compatibility.
Proposal
sort
function should have a parameter that accepts the sorting algorithm to be used to sort the collection.
This could be achieved by introducing a new protocol SortImplementation
public protocol SortImplementation {
static func sort<Element>(array: inout Array<Element>, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows
}
it will be possible at this point to define sorting algorythms as structs
struct TimSort: SortImplementation {
static func sort<Element>(array: inout Array<Element>, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
print("TimSort")
}
}
struct HeapSort: SortImplementation {
static func sort<Element>(array: inout Array<Element>, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
print("HeapSort")
}
}
struct IntroSort: SortImplementation {
static func sort<Element>(array: inout Array<Element>, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
print("IntroSort")
}
}
A SortAlgorithm
struct will group and hide actual implementations of stdlib sorting algorithms
public struct SortAlgorithm {
public static var heapSort: SortAlgorithm { return SortAlgorithm(with: HeapSort.self) }
public static var timSort: SortAlgorithm { return SortAlgorithm(with: TimSort.self) }
let implementation: SortImplementation.Type
public init<T: SortImplementation>(with implementation: T.Type) {
self.implementation = implementation
}
}
the sort function would then become something similar to this
extension Array {
mutating func sort(using implementation: SortImplementation.Type, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
try implementation.sort(array: &self, by: areInIncreasingOrder)
}
mutating func sort(using algorithm: SortAlgorithm = .timSort, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
try algorithm.implementation.sort(array: &self, by: areInIncreasingOrder)
}
}
This way the usage of sort would become:
array.sort()
array.sort(using: .heapSort)
array.sort(using: .insertionSort)
array.sort(using: .quickSort)
array.sort(using: .introSort)
//and so on...
The default sort would still be accessible in the usual way and the existing code wouldn't change. The benefits for those users that decide to use a specific sorting algorithm are that implementation details are well known, performances are predictable, changes to the swift default sorting algorithm won't affect existing code performances or memory usage.
Developers will also be able to create custom Sorting implementations just by creating a struct conformant to SortImplementation
struct CustomSort: SortImplementation {
static func sort<Element>(array: inout Array<Element>, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
print("custom sort")
}
}
and use it this way
array.sort(using: CustomSort.self)
I would include introsort, quicksort, heapsort, insertionsort and timsort.
Alternatives
Currently, special needs are addressed by developers by writing themselves the implementation of their needed sorting algorithms, risking to duplicate a sorting algorithm already implemented by the standard library, but not exposed publicly.
It's my first attempt in contributing to the swift community, so if i made mistakes in presenting the pitch, please let me know and thank you for your time.