How to effectively sort array of ordered sequences

Question

I am implementing the complex algorithm which part is sorting array of ordered sequences of numbers. The whole algorithm should be nlog(n) complexity, so this part should be same or better but I don't know how to do this.

There is an example. There is an array of sequences:

(0)
(0,1)
(0)
(0,5)
(2,4)
()
(0,5)
()
(2,4)
(1,3,4)

and final sort should be:

()
()
(0)
(0)
(0,1)
(0,5)
(0,5)
(1,3,4)
(2,4)
(2,4)

There are some important notes:

• sorting is lexicographical
• sequences are ordered but there is no guarantee for continuousness
• there are also empty sequences
• there is a lot of identical sequences
• sequences are from 0 to hundreds long, no more
• the array can be 100k long, probably no more
• final implementation will be in C++ but now it is not probably important

Can you suggest me the best way how to sort it, please? Thanks a lot

Answer 1

If you use quicksort, then the sort algorithm will be O(n log n). How you have to compare the two items is irrelevant to complexity of the sort itself, and has its own complexity (presumably O(m)).

Answer 2

If you can integrate GPLv3 code into your project, GNU Sort might be a good place to start. At least, when I ran it on your sample input, I got your sample output, so it's not immediately wrong.

Answer 3

Your problem seems similar to radix sort, in this case first sort your sequences by rightmost item (for example 100th item) if no such item exists, set it as min possible value - 1 (for example in the case I can see -1) , then sort this sorted sequence with second rightmost item, and continue this way.

Also if items in sequences all are between 1..k (in this case I can see there are between 1..9) use counting sort to sort them in O(n), if you can use counting sort, the sorting time is O(n) but else the sorting time is O(n log n).