683 views
0 votes
0 votes

Best algorithm for this set:

1.Independently sorting each of 1,000,000 arrays, each with 5 elements.

2.Sorting a set of 4,000,000 numbers in worst case O(n lg n) time.

1 Answer

2 votes
2 votes
1)  Insertion sort is applied if the number of elements are less in an array.

 from : https://www.toptal.com/developers/sorting-algorithms/insertion-sort it says

Although it is one of the elementary sorting algorithms with O(n2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

2)  Merge sort is applied when the number of elements are very very large. But it will take O(n) Space as well. It has the O(nlogn) Time complexity for all cases. Quick Sort can also be used here because Quick Sort does better partitioning than merge sort, except that the data is already sorted which is not a real task of computation to sort an already sorted array. Quick Sort will be better for logical and practical partitioning and is also in-place algorithm.

Related questions

0 votes
0 votes
1 answer
3