# Swift solution - MergeSort, BinarySearchTree, BinarySearch

• ``````class Solution {
func countSmaller_MergeSort(_ nums: [Int]) -> [Int] {
var result = [Int]()
var counts = [Int](repeatElement(0, count: nums.count))
var indexes = [Int]()

for i in 0..<nums.count {
indexes.append(i)
}
mergeSort(nums, 0, nums.count - 1, &indexes, &counts)
for i in 0..<counts.count {
result.append(counts[i])
}

return result
}

private func mergeSort(_ nums: [Int], _ start: Int, _ end: Int, _ indexes: inout [Int], _ counts: inout [Int]) {
if end <= start {
return
}

let middle = start + (end - start) / 2
mergeSort(nums, start, middle, &indexes, &counts)
mergeSort(nums, middle + 1, end, &indexes, &counts)

merge(nums, start, end, &indexes, &counts)
}

private func merge(_ nums: [Int], _ start: Int, _ end: Int, _ indexes: inout [Int], _ counts: inout [Int]) {
let middle = start + (end - start) / 2
var left = start
var right = middle + 1
var rightCount = 0
var newIndexes = [Int](repeatElement(0, count: end - start + 1))
var sortIndex = 0

while left <= middle && right <= end {
if nums[indexes[right]] < nums[indexes[left]] {
newIndexes[sortIndex] = indexes[right]
rightCount += 1
right += 1
} else {
newIndexes[sortIndex] = indexes[left]
counts[indexes[left]] += rightCount
left += 1
}
sortIndex += 1
}
while left <= middle {
newIndexes[sortIndex] = indexes[left]
counts[indexes[left]] += rightCount
left += 1
sortIndex += 1
}
while right <= end {
newIndexes[sortIndex] = indexes[right]
sortIndex += 1
right += 1
}
for i in start...end {
indexes[i] = newIndexes[i - start]
}
}

func countSmaller_BinarySearchTree(_ nums: [Int]) -> [Int] {
var result = [Int](repeatElement(0, count: nums.count))
var root: BinarySearchTreeNode? = nil

for i in stride(from: nums.count - 1, through: 0, by: -1) {
root = insert(nums[i], root, &result, i, 0)
}

return result
}

private func insert(_ num: Int, _ node: BinarySearchTreeNode?, _ result: inout [Int], _ i: Int, _ preSum: Int) -> BinarySearchTreeNode {
var node = node

if node == nil {
node = BinarySearchTreeNode(num, 0)
result[i] = preSum
} else if node!.val == num {
node?.duplicate += 1
result[i] = preSum + node!.sum
} else if node!.val > num {
node!.sum += 1
node!.left = insert(num, node!.left, &result, i, preSum)
} else {
node!.right = insert(num, node?.right, &result, i, preSum + node!.duplicate + node!.sum)
}

return node!
}

func countSmaller_BinarySearch(_ nums: [Int]) -> [Int] {
let count = nums.count
var result = [Int](repeatElement(0, count: count))
var sorted = [Int]()

for i in stride(from: count - 1, through: 0, by: -1) {
let index = binarySearch(&sorted, nums[i])
result[i] = index
sorted.insert(nums[i], at: index)
}

return result
}

private func binarySearch(_ nums: inout [Int], _ target: Int) -> Int {
if nums.count == 0 {
return 0
}

var start = 0
var end = nums.count - 1

if nums[end] < target {
return end + 1
}
if nums[start] >= target {
return 0
}
while start + 1 < end {
let middle = start + (end - start) / 2
if nums[middle] < target {
start = middle + 1
} else {
end = middle
}
}
if nums[start] >= target {
return start
}

return end
}
}

class BinarySearchTreeNode {
var left: BinarySearchTreeNode? = nil
var right: BinarySearchTreeNode? = nil
var val = 1
var sum = 1
var duplicate = 1

public init(_ val: Int, _ sum: Int) {
self.val = val
self.sum = sum
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.