big o - What would be the complexity of this Sorting Algorithm? What are the demerits of using the same? -

the sorting algorithm can described follows:

1. create binary search tree array data.

(for multiple occurences, increment occurence variable of current node)

2. traverse bst in inorder fashion.

(inorder traversal return sorted order of elements in array).

3. @ each node in inorder traversal, overwrite array element @ current index(index beginning @ 0) current node value.

here's java implementation same:

structure of node class

class node {     node left;     int data;     int occurence;     node right; } 

inorder function (returning type int obtaining correct indices @ every call, serve no other purpose)

public int inorder(node root,int[] arr,int index) {     if(root == null) return index;     index = inorder(root.left,arr,index);     for(int = 0; < root.getoccurence(); i++)         arr[index++] = root.getdata();     index = inorder(root.right,arr,index);     return index; } 

main()

public static void main(string[] args) {     int[] arr = new int[]{100,100,1,1,1,7,98,47,13,56};     binarysearchtree bst = new binarysearchtree(new node(arr[0]));     for(int = 1; < arr.length; i++)         bst.insert(bst.getroot(),arr[i]);     int dummy = bst.inorder(bst.getroot(),arr,0);     system.out.println(arrays.tostring(arr)); } 

the space complexity terrible, know, should not such big issue unless sort used extremely huge dataset. however, see it, isn't time complexity o(n)? (insertions , retrieval bst o(log n), , each element touched once, making o(n)). correct me if wrong haven't yet studied big-o well.

assuming amortized (average) complexity of insertion o(log n), n inserts (construction of tree) give o(log(1) + log(2) + ... + log(n-1) + log(n) = o(log(n!)) = o(nlogn) (stirling's theorem). read sorted array, perform in-order depth-first traversal, visits each node once, , hence o(n). combining 2 o(nlogn).

however requires tree balanced! not case in general basic binary tree, insertions not check relative depths of each child tree. there many variants self-balancing - 2 famous being red-black trees , avl trees. implementation of balancing quite complicated , leads higher constant factor in real-life performance.