Like I have input in range of 0-10^6. So first storing the integers(again in the range 0-10^6) and then sorting will certainly take a lot of time.
I was wondering whether we can sort on the go(like as the user is giving the data by standard input) and we are sorting it.
I don't want to use any standard library for this just yet(if there is any, it would be kind of you to point out).
I am certainly baffled by this problem, any help would be appreciated guys.
Inserting sorted adds more total time than sorting the entire sequence in one go. The former takes O(n^2) with insertion sort and O(n log n) with balancing trees (but a relatively slow n log n). Sorting an array takes a very fast O(n log n).
Don't do it unless you specifically need the sequence to maintain order as it's populated.
That said, the particular sorting algorithm is probably irrelevant if we're talking about sorting input that a user has to manually type in.