mergesortpractice.swift

extension Collection where Iterator.Element: Comparable {
    
    static func mergeSort(_ items: [Iterator.Element]) -> [Iterator.Element] {
        guard items.count > 1 else { return items }
        let middleIndex = items.count / 2
        let left = mergeSort(Array(items.reversed().suffix(middleIndex)).reversed().map { $0 })
        let right = mergeSort(Array(items.suffix(from: middleIndex)))
        return merge(left: left, right: right)
    }
    
    static func merge(left: [Iterator.Element], right: [Iterator.Element]) -> [Iterator.Element] {
        var leftIndex = 0
        var rightIndex = 0
        
        var orderedArray: [Iterator.Element] = []
        
        while leftIndex < left.count && rightIndex < right.count {
            let leftElement = left[leftIndex]
            let rightElement = right[rightIndex]
            
            if leftElement < rightElement {
                orderedArray.append(leftElement)
                leftIndex += 1
            } else if leftElement > rightElement {
                orderedArray.append(rightElement)
                rightIndex += 1
            } else {
                orderedArray.append(leftElement)
                leftIndex += 1
                orderedArray.append(rightElement)
                rightIndex += 1
            }
        }
        
        while leftIndex < left.count {
            orderedArray.append(left[leftIndex])
            leftIndex += 1
        }
        
        while rightIndex < right.count {
            orderedArray.append(right[rightIndex])
            rightIndex += 1
        }
        
        return orderedArray
    }
}