//
//  main.swift
//  CountInversionWithMergeSort
//
//  Created by Anthony Marchenko on 10/3/17.
//  Copyright © 2017 Anthony Marchenko. All rights reserved.
//

import Foundation

func sortAndCount(_ array : [Int]) -> ([Int], Int) {
    guard array.count > 1 else {
        return (array, 0)
    }
    
    let middleIndex = array.count / 2
    let (leftArray, leftCount)  = sortAndCount(Array(array[0..<middleIndex]))
    let (rightArray, rightCount) = sortAndCount(Array(array[middleIndex..<array.count]))
    let (finalArray, splitCount) = mergeAndCountSplitInversation(leftArray, rightArray)
    return (finalArray, leftCount + rightCount + splitCount)
}

func mergeAndCountSplitInversation(_ leftPile: [Int], _ rightPile: [Int]) -> ([Int], Int) {
    var leftIndex = 0
    var rightIndex = 0
    var orderedPile = [Int]()
    var inversationCount = 0
    
    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        if leftPile[leftIndex] <= rightPile[rightIndex] {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
        } else {
            orderedPile.append(rightPile[rightIndex])
            rightIndex += 1
            inversationCount = inversationCount + leftPile.count - leftIndex
        }
    }
    
    while leftIndex < leftPile.count {
        orderedPile.append(leftPile[leftIndex])
        leftIndex += 1
    }
    
    while rightIndex < rightPile.count {
        orderedPile.append(rightPile[rightIndex])
        rightIndex += 1
    }
    
    print("inversion for array - \(orderedPile)")
    print("count - \(inversationCount)")
    return (orderedPile, inversationCount)
}

func inverstionCountNaive (_ array :[Int]) -> Int {
    var inverstionCount = 0
    for i in 0..<array.count-1 {
        for j in i+1..<array.count {
            if array[i] > array[j] {
              inverstionCount += 1
            }
        }
    }
    
    return inverstionCount
}

let array = [2, 1, 3, 1, 2]

print("origin - \(array)")
print("sorted - \(sortAndCount(array))")
print("naive approuch count - \(inverstionCountNaive(array))")