         // Swap the pivot element with the first element that is greater than
         // the pivot. Now the pivot sits between the < and >= regions and the
         // array is properly partitioned.
-        (a[i], a[a.endIndex-1]) = (a[a.endIndex-1], a[i])
+        array.swapAt(i, hi)
         return i
-    }
-    
-    /*
-     takes an array and an index n and returns an array with the nth value being the nth largest
-     */
-    private static func quickSelect(n: Int, arr: [Element], kdDimension: Int) -> [Element] {
-        if arr.count == 1 {
-            return [arr.first!]
-        }
-        
-        var varr = arr
-        let selector = partitionLomuto(&varr[0...arr.endIndex-1], kdDimension: kdDimension)
-        
-        if selector == n {
-            return varr
-        }
-        else if n > selector {
-            let s = selector+1
-            return  Array(varr[...selector] + quickSelect(n: n, arr: varr[s...], kdDimension: kdDimension))
-        }
-        else {
-            return  Array(quickSelect(n: n, arr: varr[..<selector], kdDimension: kdDimension) + varr[selector...])
-        }
-    }
-    
-    private static func quickSelect(n: Int, arr: ArraySlice<Element>, kdDimension: Int) -> ArraySlice<Element> {
-        if arr.count == 1 {
-            return [arr.first!]
-        }
-        
-        var varr = arr
-        let selector = partitionLomuto(&varr, kdDimension: kdDimension)
-        
-        if selector == n {
-            return varr
-        }
-        else if n > selector {
-            let s = selector+1
-            return varr[..<s] + quickSelect(n: n, arr: varr[s...], kdDimension: kdDimension)
-        }
-        else {
-            return quickSelect(n: n, arr: varr[..<selector], kdDimension: kdDimension) + varr[selector...]
-        }
     }
     
     /// Returns `true` iff `self` is empty.

            self = .node(left: .leaf, value: firstValue, dimension: currentSplittingDimension, right: .leaf)
        }
        else {
            var median = values.startIndex + (values.endIndex - values.startIndex) / 2
            
            let selected = KDTree.quickSelect(n: median, arr: values, kdDimension: currentSplittingDimension)
            let medianElement = selected[median]
            let medianValue = medianElement.kdDimension(currentSplittingDimension)
            
            //Ensure left subtree contains currentSplittingDimension-coordinate strictly less than its parent node
            //Needed for 'contains' and 'removing' method.
            while median >= 1 && median > selected.startIndex && abs(selected[median-1].kdDimension(currentSplittingDimension) - medianValue) < Double.ulpOfOne {
                median -= 1
            }
            
            let leftTree = KDTree(values: selected[selected.startIndex..<median], depth: depth+1)
            let rightTree = KDTree(values: selected[median+1..<selected.endIndex], depth: depth+1)
            
            self = .node(left: leftTree, value: selected[median],
                         dimension: currentSplittingDimension, right: rightTree)
        }
    }
    

     if the pivot value occurs more than once, its duplicates will be found in the
     right partition.
     */
    private static func partitionLomuto(_ array: inout ArraySlice<Element>, kdDimension: Int) -> Int {
        let lo = array.startIndex
        let hi = array.endIndex-1
        guard lo < hi else { return 0 }
        let mid = (lo + hi) / 2
        if array[mid].kdDimension(kdDimension) < array[lo].kdDimension(kdDimension) { array.swapAt(lo, mid) }
        if array[hi].kdDimension(kdDimension) < array[lo].kdDimension(kdDimension) { array.swapAt(lo, hi) }
        if array[mid].kdDimension(kdDimension) < array[hi].kdDimension(kdDimension) { array.swapAt(mid, hi) }
        let pivot = array[hi]
        
        
        
        // This loop partitions the array into four (possibly empty) regions:
        //   [a.startIndex  ...   i] contains all values < pivot,
        //   [i+1  ...          j-1] contains all values >= pivot,
        //   [j    ..< a.endIndex-1] are values we haven't looked at yet,
        //   [a.endIndex           ] is the pivot value.
        var i = array.startIndex
        
        for j in array.startIndex..<hi {
            if array[j].kdDimension(kdDimension) < pivot.kdDimension(kdDimension) {
                array.swapAt(i, j)
                i += 1
            }
        }
