algorithm, Sorting

Question

which sorting algorihm is used if we have a telephone directory wit 1,00,000 entries ?

Comments

The best algorithm to sort 100000 entries of a telephone directory is Radix sort.
Considering each number is 10 digit, the run time of radix sort is O(n*k) , i.e, O(10⁶)

If we use merge-sort to sort the directory, then the run time is O(nlgn) i,e, O(10⁵ x 13.28) i.e, O(1.3x10⁶)

 

---

Make this an answer.

Answer 1

we should use heap sort or even merge sort can be used

Comments

yes i understand your logic that merge and heap work better for larger inputs. but,

the answer is Bucket sort. please anyone can explain this?

---

Actually, the algorithm is decided based upon how much information do we have about the data. If we dont have any information about the data whatsoever that is about to sort, its better to apply merge sort. Now if suppose the data to be sorted is not already sorted we should apply quick sort for its better partitioning the data for recursive calls. Now, the question says telephone directory, the answer bucket sort might be correct because bucket sort is applied when there is chunks of data that is already sorted or in close range and maybe you could think of telephone directory numbers that are very close to each other in a region or so. That makes the data fit for bucket sort.