MergeSort playground

MergeSort.playground

//: Playground - noun: a place where people can play

import UIKit

func mergeArrays<T: Comparable>(left: [T], _ right: [T]) -> [T] {
    var leftIndex = 0
    var rightIndex = 0
    var orderedArray = [T]()
    
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            orderedArray.append(left[leftIndex++])
        } else if left[leftIndex] > right[rightIndex] {
            orderedArray.append(right[rightIndex++])
        } else {
            orderedArray.append(left[leftIndex++])
            orderedArray.append(right[rightIndex++])
        }
    }
    
    orderedArray = orderedArray + Array(left[leftIndex..<left.count])
    orderedArray = orderedArray + Array(right[rightIndex..<right.count])
    return orderedArray
}

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

    guard array.count > 1 else {
        return array
    }
    
    let bound = array.count / 2

    let left = array[0..<bound]
    let right = array[bound..<array.count]
    
    return mergeArrays(mergeSort(Array(left)), mergeSort(Array(right)))
}

// Verify & Bench
func verify<T: Comparable>(@autoclosure lhs: () -> [T], equalTo rhs: [T]) -> CFTimeInterval {
    let time = CACurrentMediaTime()
    let result = lhs()
    let diff = CACurrentMediaTime() - time
    assert(result.elementsEqual(rhs))
    return diff
}

// Tests
verify(mergeSort([Int]()), equalTo: [Int]())
verify(mergeSort([2,2]), equalTo: [2,2])
verify(mergeSort([2,3]), equalTo: [2,3])
verify(mergeSort([3,2]), equalTo: [2,3])
verify(mergeSort([2,3,4]), equalTo: [2,3,4])
verify(mergeSort([2,4,3]), equalTo: [2,3,4])
verify(mergeSort([2,2,2]), equalTo: [2,2,2])
verify(mergeSort([8,9,6,7,5,4,3,2,0,1]), equalTo: [0,1,2,3,4,5,6,7,8,9])
verify(mergeSort([8,9,6,7,0,0,0,2,0,1]), equalTo: [0,0,0,0,1,2,6,7,8,9])
verify(mergeSort([8,9,6,7,-0.1,-0.3,-0.4,2,0,1]), equalTo: [-0.4,-0.3,-0.1,0,1,2,6,7,8,9])