Few methods of sorting implemented in swift

sort_methods.swift

// O(n2)
func selectionSort(array: [Int]) -> [Int] {

   var copy = array

    for index in 0..<copy.count - 1 {
        let subarray = copy.suffix(from: index + 1)
        let min = subarray.min()!
        if min < copy[index] {
            let indexOfMin = subarray.firstIndex(of: min)!
            copy.swapAt(index, indexOfMin)
        }
    }

    return copy
}

// O(n2) - worst and average
// O(n) - best 
func insertionSort(array: [Int]) -> [Int] {
    var copy = array

    for index in 1..<copy.count {
        for tempIndex in (1...index).reversed() {
            if copy[tempIndex] < copy[tempIndex - 1] {
                copy.swapAt(tempIndex, tempIndex-1)
            } else {
                break
            }
        }
    }

    return copy
}

// O(n log n) - average and worst
func mergeSort(array: [Int]) -> [Int] {
    if array.count <= 1 {
        return array
    }

    let middleIndex = Int(array.count / 2)

    let arrayA = array.prefix(upTo: middleIndex).map { $0 }
    let arrayB = array.suffix(from: middleIndex).map { $0 }

    let arrayASorted = mergeSort(array: arrayA)
    let arrayBSorted = mergeSort(array: arrayB)

    return mergeSortedArrays(arrayASorted, arrayBSorted)
}

func mergeSortedArrays(_ arrayA: [Int], _ arrayB: [Int]) -> [Int] {
    var indexA = 0
    var indexB = 0

    // possible improvement: initialize array of correct size right away
    var temp = [Int]()

    while indexA < arrayA.count, indexB < arrayB.count {
        if arrayA[indexA] < arrayB[indexB] {
            temp.append(arrayA[indexA])
            indexA += 1
        } else {
            temp.append(arrayB[indexB])
            indexB += 1
        }
    }

    if indexA < arrayA.count {
        temp.append(contentsOf: arrayA.suffix(from: indexA))
    } else if indexB < arrayB.count {
        temp.append(contentsOf: arrayB.suffix(from: indexB))
    }

    return temp
}

// O(n log n) - average
// O(n2) - worst case scenario 
func quickSort(array: inout [Int], lowerIndex: Int, upperIndex: Int) -> [Int] {
    guard array.count > 1, lowerIndex < upperIndex else {
        return array
    }

    let pivot = array[lowerIndex]
    var lowerBound = lowerIndex + 1
    var upperBound = upperIndex

    while lowerBound <= upperBound {

        if array[upperBound] <= pivot {

            if array[lowerBound] > pivot {
                array.swapAt(lowerBound, upperBound)
            }

            lowerBound += 1
        } else {
            upperBound -= 1
        }
    }

    array.swapAt(lowerIndex, lowerBound - 1)

    quickSort(array: &array, lowerIndex: lowerIndex, upperIndex: lowerBound - 2)
    quickSort(array: &array, lowerIndex: lowerBound, upperIndex: upperIndex)

    return array
}

// ( ͡° ͜ʖ ͡°)
// O(∞)
func bogoSort(array: [Int]) -> [Int] {
    var sorted = false
    var temp = array
    
    while !sorted {
        temp = array.shuffled()
        sorted = true
        
        for i in temp.indices.dropLast() {
            if temp[i] > temp[i + 1] {
                sorted = false
                break
            }
        }
    }
    
    return temp
}