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
std::sort
andstd::lexicographical_compare
. This will give you the desired complexity and you can be reasonably sure the code will work.std::sort
and thank you for pointing outstd::lexicographical_compare
, I didn't know it.