What is the best sort algorithm for continuously (NOT FIXED) input of random numbers?

Question

Suppose I have a system that receives one by one as an input continuously random numbers all the time (0,5,2,10,6,20......) ,

My purpose is to sort them with the best performance.

So the output size will be increased after each iteration and the input is sequential .

I thought to use either insertion sort or BST , but I don't sure what is better for this issue ,as i know insertion sort is O(n-n^2) and BST insertion is O(log(n))

Please , any suggestions ?

Answer 1

If you need to sort every time an element is added, this is not a sorting problem but an insertion problem. Any sorting algorithm will be overkill.

If your data must be stored in an array, you can't spare shifting the elements and the solution is Ω(N). This is efficiently achieved by straight insertion (O(N)). (Dichotomic search followed by insertion will take less comparisons but it is not sure that you will notice a difference.)

If you have more freedom, a BST is indeed a more efficient solution. If you need absolute guarantee on the worst-case cost (O(Log N)), the BST needs to be balanced (so AVL, Red-Black... up to your taste). If your data is sufficiently random, this might be unnecessary.

If your data has special properties (for example small discrete range), ad-hoc solutions can do. In the given example, a simple counting histogram will achieve O(1) update time.