Question

Suppose you need to sort 10 million integers, each in the range 0 to 2⁴⁰. How would you do it? Which of the following method gives the smallest tilde time complexity and why?
a) Insertion sort
b) Mergesort
c) Quicksort
d) LSD radix sort
e) Key-indexed counting sort

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

We should use key indexed counting sort since it will give time complexity of O(n) where n is number of integers

The steps are as follows

a) Initialize an array of 241 integers with default 0

b) Now for all 10 million integers map it to the array A which is initially 0 A[arr[i]]++;

c) Now print the indexes of array the number of times it is having the value at index of A

Kindly revert for any queries

Thanks.