Pre order traversal of an array I am wondering if there is an algorithm that, given a sorted array, allows you to build a binary search tree in linear time?

I am facing a problem where I have about 8 million elements in a file that need to be loaded into a BST so O(n) would be vastly preferable to O(n log n) if it's possible.
I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which will be the left child of the central element, and equivalently the tree resulting from the right subarray will be the right child.

By induction you can prove that the resulting tree is balanced since you are building trees of the same size at each side (+/- 1 node). Also is easy to prove that the result is a binary search tree, by construction.

With respect to the complexity, every node in the recursive execution tree takes constant time. Since you have a number of nodes proportional to the number of elements in your input, then the algorithm is O(n).