# Swift solution - Merge Sort

• ``````class Solution {
func countRangeSum(_ nums: [Int], _ lower: Int, _ upper: Int) -> Int {
let count = nums.count
var sums = [Int](repeatElement(0, count: count + 1) )

for i in 0..<count {
sums[i + 1] = sums[i] + nums[i]
}

return mergeSort(&sums, 0, count + 1, lower, upper)
}

private func mergeSort(_ sums: inout [Int], _ start: Int, _ end: Int, _ lower: Int, _ upper: Int) -> Int {
if end - start <= 1 {
return 0
}

let middle = start + (end - start) / 2
var count = mergeSort(&sums, start, middle, lower, upper) + mergeSort(&sums, middle, end, lower, upper)
var j = middle
var k = middle
var t = middle
var cache = [Int](repeatElement(0, count: end - start))
var r = 0

for i in start..<middle {
while k < end && sums[k] - sums[i] < lower {
k += 1
}
while j < end && sums[j] - sums[i] <= upper {
j += 1
}
while t < end && sums[t] < sums[i] {
cache[r] = sums[t]
r += 1
t += 1
}
cache[r] = sums[i]
count += (j - k)
r += 1
}

for i in 0...(t - start - 1) {
sums[i + start] = cache[i]
}

return count
}
}
``````

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