Best data structure to store one million values?

Question

Please mention time complexity and best data structure to store these values, when values are:

1. Integers
2. Strings (dictionary like sorting)

I know Counting sort is preferred when integers are in a small range.

Thanks.

Edit: Sorry, I asked a bit different question. Actual question is what would be the best data structure to store these values, if the integers are phone numbers (and strings are names) and then find the best sorting algorithm.

Answer 1

Sorting algorithms wiki link: Sorting Algorithm Wiki

Merge sort and quick sort are pretty good, they are n log n in best cases.

Answer 2

Have a look at: Btrees and red-black trees.

You should be able to find open source implementations of each of these. (Note, I'm assuming that you want to maintain a sorted structure, rather than just sorting once and forgetting.)

Answer 3

How about a heap? Relatively easy to implement and pretty fast. For strings, you could use a Trie along with something like Burst sort which is supposedly the fastest string sorting algorithm in its class.

Answer 4

For most sorting algorithms there is an in-place version, so a simple array may be sufficient. For Strings you may consider a http://en.wikipedia.org/wiki/Trie, which could save space. The right sorting algorithm depends on a lot of factors, e.g. if the results may be already sorted or partially sorted. Of course if you have just a few different values, Countingsort, Bucketsort etc can be used.

Answer 5

On a 32-bit machine, a million integers can fit in an array of 4 million bytes. 4MB isn't all that much; it'll fit in this system's memory 500 times over (and it's not that beefy by modern standards). A million strings will be the same size, except for the storage space for those strings; for short strings it's still no problem, so slurp it all in. You can even have an array of pointers to structures holding an integer and a reference to a string; it will all fit just fine. It's only when you're dealing with much more data than that (e.g., a billion items) that you need to take special measures, data-structure-wise.

For sorting that many things, choose an algorithm that is O(nlogn) instead of one that is O(n²). The O(n) algorithms are only useful when you've got particularly compact key spaces, which is pretty rare in practice. Choosing which algorithm from the set that are in O(nlogn) is a matter of balancing speed and other good properties such as stability.

If you're doing this for real, use a database with appropriate indices instead of futzing around with doing this all by hand.