How do you implement a merge sort in Swift as a generic protocol extension?

Answer 1

Assuming that this question is about the semantics of creating a generic protocol extension to implement a problem solving question and not the fundamentals behind merge sort (you can read up merge sort here: https://www.geeksforgeeks.org/merge-sort/).

Most students struggle with the 'generic' concept of a generic protocol extension, since it is not specified, I will assume there is ample knowledge on:

(1) what a protocol is (https://docs.swift.org/swift-book/LanguageGuide/Protocols.html) and

(2) an extension in swift (https://docs.swift.org/swift-book/LanguageGuide/Extensions.html)

- if not feel free to setup sometime w/ me as these are a bit more in depth than "Ask an Expert" is for -

Generics

The concept of something being "generic" in the context of methods, functions, protocols, and most computer science terminology, is reference to the ability for some aspect to be dynamic. This means a programmer, like yourself, is required to specify a type when implementing a "generic" [enter some CS terminology listed above here]. The denotation of <T> is often used for generics, so it can be a helpful indicator.

For example, a generic parameter clause (a necessity for this problem, see code below) is

denoted by

<generic_parameter_list>: a comma-separated list of generic parameters, i.e. <generic_parameter, generic_parameter2, etc>

generic_parameter: a type parameter followed by an optional constraint. i.e. T: Comparable

type_parameter: a name of a placeholder type i.e. T, U, V, Key, Value etc.

optional_constraint: articulates a type_parameter inherits from a specific class or conforms to a protocol (or protocol composition) i.e. Comparable protocol.

/** Standard Merge Sort Method Signature

- parameter list: an unsorted array of Integers

- return: a sorted array of Integers

*/

func mergeSort(_ list: [Int]) -> [Int] {

// Merge sort algorithm goes here

}

/** Generic Type Parameter Method Signature

- parameter list: an array of a generic type 'T' which must conform to the 'Comparable' protocol

- return: a sorted array of type 'T'

*/

func mergeSort<T: Comparable>(_ list: [T]) -> [T] {

// Merge sort algorithm goes here

}

- Generic Parameters: https://docs.swift.org/swift-book/ReferenceManual/GenericParametersAndArguments.html

- Generics: https://docs.swift.org/swift-book/LanguageGuide/Generics.html

Essentially, everywhere we used the type "'nt', we replace with 'T' because that is the new type we want.

Note: Many types conform to the protocol 'Comparable', you can use Apple's documentation to see if it does. i.e. Int, Double etc. (https://developer.apple.com/documentation/swift/comparable)

/** Example of what generic allows us to do: use the same function for different types that all share a particular characteristic if specified i.e. Comparable */

int main() {

print(mergeSort([1, 4, 2, 5, 8]))

// >> output: [1, 2, 4, 5, 8]

print(mergeSort([1.5, 4.0, 2.3, 9.3, 4.5]))

// >> output: [1.5, 2.3, 4.0, 4.5, 9.3]

}

If you want to see a full implementation you can find one here: https://www.raywenderlich.com/741-swift-algorithm-club-swift-merge-sort