How can you sort an array of integers lexicographically?

Question

I want to sort a large array of integers (say 1 millon elements) lexicographically.

Example:

int input [] = { 100, 21 , 22 , 99 , 1  , 927 }
int sorted[] = { 1  , 100, 21 , 22 , 927, 99  }

I have done it using the simplest possible method:

• convert all numbers to strings (very costly because it will take huge memory)
• use std:sort with strcmp as comparison function
• convert back the strings to integers

Is there a better method than this?

Answer 1

Use std::sort() with a suitable comparison function. This cuts down on the memory requirements.

The comparison function can use n % 10, n / 10 % 10, n / 100 % 10 etc. to access the individual digits (for positive integers; negative integers work a bit differently).