Worst Case Binary Tree - Determine "Sorted-ness"

Question

In the worst case, creating a binary tree from a known list will be O(n²), but the average case is O(n logn). The difference between the worst case and the average case depends on how unbalanced the tree is after creation. If maxDepth == n, then this is the worst case and if maxDepth == log(n) then this is the best case. Knowing maxDepth before building the tree would give a lot of insight into the running time of creating the tree.

Max Depth

Is there a way to determine max-depth (or an approximation) in O(n) time? I could not think of a way to do this. Instead I opted to try and find the "sorted-ness" of the initial list.

Sorted-ness

In the worst case example of a binary tree, a sorted list will end up being functionally equivalent to a linked-list. The more sorted the list is, the worse the performance of the binary tree. I could not find anything that would give a "sort-factor" of a list. The algorithm I tried worked for what I needed, but it doesn't feel "right"*.

public double sortFactor(int[] ar) {
    //assume lists are larger than 10000 elements
    int prevSum = ar[0] + ar[1] + ar[2];
    int numIncreasing = 0;
    for(int i=3; i < ar.length-3; i+=3) {
        int sum = ar[i] + ar[i+1] + ar[2];
        if (sum > prevSum) {
            numIncreasing++;
        }
        prevSum = sum;
    }
    int totalSets = ar.length/3;
    double sortFactor = (double) numIncreasing / (double) totalSets;
    return sortFactor;
}

*"right" - This algorithm isn't based on any proof or concept that sits on solid ground. Its based on fuzzing the data to see if groups of 3 are in sorted to semi-sorted order. 3 was chosen because it is larger than both 1 and 2.

Questions

Is there a way to determine max-depth(or an approximation) of a future binary tree based on given list in O(n) time?

Is "sorted-ness" a determinable property of a list? Can it be determined in O(n) time or would this require a much larger time complexity space?

Disclaimer

I am aware of self-balancing binary trees (Red-Black, AVL), but for the purposes of this question they are uninteresting. They do not relate to either of the questions above, but rather solve the background information on where those two questions originated.

Answer 1

It certainly can be done in time O(n log n). I'm skeptical about O(n) in the linear decision tree model, but I don't have any evidence.

Keep a sorted map from the intervals between existing keys to the depth at which the new node would be inserted. For each point in order, find its interval and split into two at depth plus one.

Example execution on 3, 1, 4, 5, 9:

(-inf, inf): 0

insert 3

(-inf, 3): 1
(3, inf): 1

insert 1

(-inf, 1): 2
(1, 3): 2
(3, inf): 1

insert 4

(-inf, 1): 2
(1, 3): 2
(3, 4): 2
(4, inf): 2

insert 5

(-inf, 1): 2
(1, 3): 2
(3, 4): 2
(4, 5): 3
(5, inf): 3

insert 9

(-inf, 1): 2
(1, 3): 2
(3, 4): 2
(4, 5): 3
(5, 9): 4
(9, inf): 4

for an answer of depth 4 (including the null nodes). Here's the tree (* denotes null):

      3
     / \
    /   \
   /     \
  1       4
 / \     / \
*   *   *   5
           / \
          *   9
             / \
            *   *