Treesort sorts input by putting input into a binary search tree and then flattening the tree. In some cases the tree can become unbalanced and so a self-balancing tree is required. There is no requirement for a self-balancing tree if the input is first randomly jumbled up first. However, one cannot shuffle a stream of data without waiting for all the data which is undesirable sometimes.
If I take inputs two at a time and randomly swap them before inserting them how unbalanced will the tree tend to become over time?