A researcher has a database of 100 million records of people. The researcher wants to study the distribution of given names according to other criteria such as zodiac sign, birth year, etc, so wants to sort by name with the option of further sorting later.
Which sort should I use?
A. selection
B. quick
C. heap
D. insertion
E. merge
Thanks!
It's not really my answer since you reached it yourself, but here it is for better visibility:
O(n^2)
average running time, which isn't going to cut it for 100M items.Update: Exam-related advice
I have to admit that point 2 above (preserve the sort by name) is not totally clear from the problem description. However, this is an exam question and there has to be some way of trimming the options down to one. This is only made possible by demanding a stable sort, so the requirement is there even if the wording is not ironclad.
This way of practical thinking makes it IMHO much easier to reach definitive answers for some types of exam questions.
Try mapping your requirements to the comparison table at http://en.wikipedia.org/wiki/Sort_algorithms#Comparison_of_algorithms.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With