//A review thanks to http://bost.ocks.org/mike/algorithms/

import Foundation

func exchange<T>(inout elementsIn array: [T], i: Int, j: Int)
{
    let temp: T = array[i]
    array[i] = array[j]
    array[j] = temp
}

///Fisher-Yates Shuffle
///:param: array Array to shuffle
func shuffle<T>(inout array: [T])
{
    var n = array.count
    
    while(n > 0) {
        //arc4random() doesn't work
        let index = Int(rand()) % n--
        exchange(elementsIn: &array, i: index, j: n)
    }
}

///Insertion Sort
///:param: array Array to sort
func insertionSort<T: Comparable>(inout array: [T])
{
    for var i = 1; i < array.count; ++i {
        for var j = i; j > 0; --j {
            if array[j-1] > array[j] {
                exchange(elementsIn: &array, i: j-1, j: j)
            }
        }
    }
}

///Quick Sort
///:param: array Array to sort
func quickSort<T: Comparable>(inout array: [T], left: Int, right: Int)
{
    if left < right - 1 {
        var pivot: Int = (left + right) >> 1
        pivot = part(&array, left: left, right: right, pivot: pivot)
        quickSort(&array, left: left, right: pivot)
        quickSort(&array, left: pivot + 1, right: right)
    }
}

func part<T: Comparable>(inout array: [T], left: Int, right: Int, pivot: Int) -> Int
{
    let pivotValue: T = array[pivot]
    var l = left, r = right
    
    exchange(elementsIn: &array, i: pivot, j: --r)
    for var i: Int = l; i < r; ++i {
        if array[i] < pivotValue {
            exchange(elementsIn: &array, i: i, j: l++)
        }
    }
    exchange(elementsIn: &array, i: l, j: r)
    return l
}

///Merge Sort(Bottom Up)
///:param: array Array to sort
func mergeSort<T: Comparable>(inout array: [T])
{
    let n = array.count
    var a0 = array
    var a1 = Array<T>()
    for idx in 0...n-1 {
        a1.append(a0[idx])
    }
    
    for var m = 1; m <= n; m <<= 1{
        for var i = 0; i < n; i += m << 1 {
            let left = i, right = min(i + m, n), end = min(i + (m << 1), n)
            merge(&a0, a1: &a1, left: left, right: right, end: end)
        }
        array = a0
        a0 = a1
        a1 = array
    }
    
}

func merge<T: Comparable>(inout a0: [T], inout a1: [T], left: Int, right: Int, end: Int)
{
    var i0 = left
    var i1 = right
    
    for var j = left; j < end; ++j {
        if i0 < right && (i1 >= end || a0[i0] <= a0[i1]) {
            a1[j] = a0[i0++]
        } else {
            a1[j] = a0[i1++]
        }
    }
}

var a = [1,2,3,4,5,8,9,6]

shuffle(&a)
a
mergeSort(&a)
a