I want to construct KD-Tree from unsorted List of points in the plane (i.e. 2-KD-Tree). To do so I used the method from Wikipedia: http://en.wikipedia.org/wiki/Kd-tree#Construction  This is my code:public static Node buildKDTree(List<Node> list, boolean depth){    if(depth){        Collections.sort(list, Node.xComparator);    }    else{        Collections.sort(list, Node.yComparator);    }    int middle = list.size()/2;    Node root = list.get(middle);    List<Node> left = new ArrayList<Node>();    for (int i = 0; i < middle; i++) {        left.add(list.get(i));    }    List<Node> right = new ArrayList<Node>();    for (int i = middle+1; i < list.size(); i++) {        right.add(list.get(i));    }    root.leftChild = buildKDTree(left, !depth);    depth = !depth;    root.rightChild = buildKDTree(right, !depth);    return root;}The implementation of Node class is not impotrant (I think). What I dont like in my code is that in each iteration I spend O(n) time to copy the first half of the sorted list into new list (left) and then do the same for the other half of the list(right). Is there any way to avoid this? I was thinking to include indexes begin and end as parameters to my method but I dont see how it would speed up, since I dont know method for collectios that will sort the collection partly, i.e. from begin to middle and then from middle to end. 
Construct KD-Tree in Java
java;tree;collections;complexity;clustering