             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 sliceStartIndex = values.startIndex
+            let sliceEndIndex = values.endIndex
+            var median = sliceStartIndex + (sliceEndIndex - sliceStartIndex) / 2
+            
+            let selected = KDTree.quickSelect(targetIndex: median, array: 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 {
+            while median >= 1 && median > sliceStartIndex && 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)
+            let leftTree = KDTree(values: selected[sliceStartIndex..<median], depth: depth+1)
+            let rightTree = KDTree(values: selected[median+1..<sliceEndIndex], depth: depth+1)
             
             self = .node(left: leftTree, value: selected[median],
                          dimension: currentSplittingDimension, right: rightTree)
+        }
+    }
+    
+    private static func quickSelect(targetIndex: Int, array: ArraySlice<Element>, kdDimension: Int) -> ArraySlice<Element> {
+        guard array.count > 1 else { return array }
+        
+        var varray = array
+        let partitionIndex = KDTree.partitionLomuto(&varray, kdDimension: kdDimension)
+        
+        if partitionIndex == targetIndex {
+            return varray
+        } else if partitionIndex < targetIndex {
+            let s = partitionIndex+1
+            return varray[...partitionIndex] + quickSelect(targetIndex: targetIndex, array: varray[s...], kdDimension: kdDimension)
+        } else {
+            // partitionIndex is greater than the targetIndex, quickSelect moves to indexes smaller than partitionIndex
+            return quickSelect(targetIndex: targetIndex, array: varray[..<partitionIndex], kdDimension: kdDimension) + varray[partitionIndex...]
         }
     }
     

        else {
            var median = values.count / 2
            
            let selected = KDTree.quickSelect(n: median, arr: values, kdDimension: currentSplittingDimension)
            let medianElement = selected[median]
            let medianValue = medianElement.kdDimension(currentSplittingDimension)
          

        // 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.
        array.swapAt(i, hi)
        return i
    }
    
    /// Returns `true` iff `self` is empty.
