1

I would like to know the best way to sort a long list of strings wrt the time and space efficiency. I prefer time efficiency over space efficiency.

The strings can be numeric, alpha, alphanumeric etc. I am not interested in the sort behavior like alphanumeric sort v/s alphabetic sort just the sort itself.

Some ways below that I can think of.

  1. Using code ex: .Net framework's Arrays.Sort() function. I think the way this works is that the hashcodes for the strings are calculated and the string is inserted at the proper position using a binary search.

  2. Using the database (ex: MS-sql). I have not done this. I do not know how efficient this would be though.

  3. Using a prefix tree data structure like a trie. Sorting requires traversing all the trieNodes of the trie tree using DFS (depth first search) - O(|V| + |E|) time. (Searching takes O(l) time where l is the length of the string to compare).

Any other ways or data structures?

1
  • looking for language independent solution
    – hIpPy
    Jun 18, 2010 at 21:09

4 Answers 4

1

You say that you have a database, and presumably the strings are stored in the database. Then you should get the database to do the work for you. It may be able to take advantage of an index and therefore not need to actually sort the list, but just read it from the index in sorted order.

If there is no index the database might still be able to help you. If you only fetch the first k rows for some small constant number k, for example 100. When you use ORDER BY with a LIMIT clause it allows SQL Server to use a special optimization called TOP N SORT which runs in linear time instead of O(n log(n)) time.

If your strings are not in the database already then you should use the features provided by .NET instead. I think it is unlikely you will be able to write custom code that will be much faster than the default sort.

1
  • 1
    database sort would NOT be the most efficient in all cases.
    – hIpPy
    Jul 8, 2010 at 18:03
1

I found this paper that uses trie data structure to efficiently sort large sets of strings. I have not looked into it in detail though.

0

Radix sort could also be good option if strings are not very long e.g. list of names

0

Let us suppose you have a large list of strings and that the length of the List is N.

Using a comparison based sorting algorithm like MergeSort, HeapSort or Quicksort will give you an enter image description here

where n is the size of the list and d is the maximum length for all strings in the list.

We can try to use Radix sort in this case. Let b be the base and let d be the length of the maximum string then we can show that the running time using radix sort is enter image description here.

Furthermore, if the strings are say the lower case English Alphabets the running time is O(n*d+26d)

Source: MIT Opencourse Algorithms lecture by prof. Eric Demaine.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.