I have a very large data of integers which is given by the user. I have to sort these integers and then output the sorted integers. If I use an insertion sort (in place) and as the user inputs values, insert it in an apropriate place in the array, would it be faster than taking the elements in an array and then sorting them by quick sort?
No, that wouldn’t be faster. Time complexity will not change for insertion sort, so why increase the space also. Use mergesort instead, if the data set is not that large. Radix sort can be a potential improvement.
Other options:
If you are not having any space constraint, then you can create a BST of the numbers of the scanned numbers. Insert the next number in BST , will give you logarithmic time complexity. However, I believe, such questions depends on certain input constraints. Like, if you are given that input is in some permissible valid(small) range, we can always go for counting sort.
Also, we can do this: decide some size for dividing the input in fixed-size chunks. Sort these chunks using the appropriate sorting algorithm(as per your chunk size) and then merge all of them. See, External Sorting wiki for more clearance on this.
Thank You!