Swift 3.0 归并排序

归并排序：

1. 将序列每相邻两个数字进行归并操作，形成 floor ( n/2
   ) 个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成 floor ( n/4
   )
   个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕

MergeSort.swift如下：

//归并排序 从小到大排序

var a = [6, 5, 4, 3, 2, 1]
print("a is \(a)")

func merge( array:inout [Int], first:Int, mid:Int, last:Int){
    print("")
    print("merge called: array is \(array), first is \(first), mid is \(mid), last is \(last)")
    
    var tempArray = Array<Int>()
    var indexA = first
    var indexB = mid
    while indexA < mid && indexB < last {
        if array[indexA] < array[indexB]{
            tempArray.append(array[indexA])
            print("append \(array[indexA]) to tempArray while indexA \(indexA) < mid \(mid) && indexB \(indexB) < last \(last) and array[indexA] \(array[indexA]) < array[indexB] \(array[indexB])")
            indexA += 1
        }else{
            tempArray.append(array[indexB])
            print("append \(array[indexB]) to tempArray while indexA \(indexA) < mid \(mid) && indexB \(indexB) < last \(last) and array[indexA] \(array[indexA]) >= array[indexB] \(array[indexB])")
            indexB += 1
        }
    }
    
    while indexA < mid {
        tempArray.append(array[indexA])
        print("append \(array[indexA]) to tempArray while indexA \(indexA) < mid \(mid) ")
        indexA += 1
    }
    
    while indexB < last{
        tempArray.append(array[indexB])
        print("append \(array[indexB]) to tempArray while indexB \(indexB) < last \(last) ")
        indexB += 1
    }
    print("tempArray is \(tempArray)")
    
    var index = 0
    for item in tempArray{
        array[first + index] = item
        index += 1
    }
    
    print("")
    print("merge finished: array is \(array), first is \(first), mid is \(mid), last is \(last)")
    print("")
}

func mergeSort(array:inout [Int], first:Int, last:Int){
    if first+1 < last{
        print("")
        print("====== start mergeSort loop")
        
        let mid = (first + last)/2
        
        print("first is \(first), last is \(last), mid is \(mid), array is \(array)")
        
        mergeSort(array: &array, first: first, last: mid)
        mergeSort(array: &array, first: mid, last: last)
        merge(array: &array, first: first, mid: mid, last: last)
        
        print("array now is \(array)")
    } else {
        print("-- end mergeSort loop, now first is \(first), last is \(last), array is \(array)")
    }
}

print("")

mergeSort(array:&a, first:0, last: a.count)
//merge(array:&a, first: 0, mid:3, last:a.count)

print("")
//排序完成
print("sorted a is \(a)")

Terminal运行swift MergeSort.swift可以看到：

a is [6, 5, 4, 3, 2, 1]


====== start mergeSort loop
first is 0, last is 6, mid is 3, array is [6, 5, 4, 3, 2, 1]

====== start mergeSort loop
first is 0, last is 3, mid is 1, array is [6, 5, 4, 3, 2, 1]
-- end mergeSort loop, now first is 0, last is 1, array is [6, 5, 4, 3, 2, 1]

====== start mergeSort loop
first is 1, last is 3, mid is 2, array is [6, 5, 4, 3, 2, 1]
-- end mergeSort loop, now first is 1, last is 2, array is [6, 5, 4, 3, 2, 1]
-- end mergeSort loop, now first is 2, last is 3, array is [6, 5, 4, 3, 2, 1]

merge called: array is [6, 5, 4, 3, 2, 1], first is 1, mid is 2, last is 3
append 4 to tempArray while indexA 1 < mid 2 && indexB 2 < last 3 and array[indexA] 5 >= array[indexB] 4
append 5 to tempArray while indexA 1 < mid 2 
tempArray is [4, 5]

merge finished: array is [6, 4, 5, 3, 2, 1], first is 1, mid is 2, last is 3

array now is [6, 4, 5, 3, 2, 1]

merge called: array is [6, 4, 5, 3, 2, 1], first is 0, mid is 1, last is 3
append 4 to tempArray while indexA 0 < mid 1 && indexB 1 < last 3 and array[indexA] 6 >= array[indexB] 4
append 5 to tempArray while indexA 0 < mid 1 && indexB 2 < last 3 and array[indexA] 6 >= array[indexB] 5
append 6 to tempArray while indexA 0 < mid 1 
tempArray is [4, 5, 6]

merge finished: array is [4, 5, 6, 3, 2, 1], first is 0, mid is 1, last is 3

array now is [4, 5, 6, 3, 2, 1]

====== start mergeSort loop
first is 3, last is 6, mid is 4, array is [4, 5, 6, 3, 2, 1]
-- end mergeSort loop, now first is 3, last is 4, array is [4, 5, 6, 3, 2, 1]

====== start mergeSort loop
first is 4, last is 6, mid is 5, array is [4, 5, 6, 3, 2, 1]
-- end mergeSort loop, now first is 4, last is 5, array is [4, 5, 6, 3, 2, 1]
-- end mergeSort loop, now first is 5, last is 6, array is [4, 5, 6, 3, 2, 1]

merge called: array is [4, 5, 6, 3, 2, 1], first is 4, mid is 5, last is 6
append 1 to tempArray while indexA 4 < mid 5 && indexB 5 < last 6 and array[indexA] 2 >= array[indexB] 1
append 2 to tempArray while indexA 4 < mid 5 
tempArray is [1, 2]

merge finished: array is [4, 5, 6, 3, 1, 2], first is 4, mid is 5, last is 6

array now is [4, 5, 6, 3, 1, 2]

merge called: array is [4, 5, 6, 3, 1, 2], first is 3, mid is 4, last is 6
append 1 to tempArray while indexA 3 < mid 4 && indexB 4 < last 6 and array[indexA] 3 >= array[indexB] 1
append 2 to tempArray while indexA 3 < mid 4 && indexB 5 < last 6 and array[indexA] 3 >= array[indexB] 2
append 3 to tempArray while indexA 3 < mid 4 
tempArray is [1, 2, 3]

merge finished: array is [4, 5, 6, 1, 2, 3], first is 3, mid is 4, last is 6

array now is [4, 5, 6, 1, 2, 3]

merge called: array is [4, 5, 6, 1, 2, 3], first is 0, mid is 3, last is 6
append 1 to tempArray while indexA 0 < mid 3 && indexB 3 < last 6 and array[indexA] 4 >= array[indexB] 1
append 2 to tempArray while indexA 0 < mid 3 && indexB 4 < last 6 and array[indexA] 4 >= array[indexB] 2
append 3 to tempArray while indexA 0 < mid 3 && indexB 5 < last 6 and array[indexA] 4 >= array[indexB] 3
append 4 to tempArray while indexA 0 < mid 3 
append 5 to tempArray while indexA 1 < mid 3 
append 6 to tempArray while indexA 2 < mid 3 
tempArray is [1, 2, 3, 4, 5, 6]

merge finished: array is [1, 2, 3, 4, 5, 6], first is 0, mid is 3, last is 6

array now is [1, 2, 3, 4, 5, 6]

sorted a is [1, 2, 3, 4, 5, 6]

源码引用参考[http://panl.github.io/2015/12/10/Algorithm/]
资料引用[https://zh.wikipedia.org/wiki/归并排序#C.2B.2B]