I would like to sort an array of tuples by all elements (like if they were in a trie). If the input is (1,2,5), (1,2,3), (1,1,4), (2,8,9), the corresponding output would be (1,1,4), (1,2,3), (1,2,5),(2,8,9). The corresponding trie would be:
root
/ \
1 2
/ \ |
1 2 8
| /\ |
4 3 5 9
I was thinking about using a search tree for each position in the tuples. There is also the obvious naive way (sort by first position, then sort by second position, etc.). Does anybody see a better way?
The trie-based approach that you have outlined above is extremely similar to doing a most-significant digit radix sort on the tuples. You essentially are distributing them into buckets based on their first digit, then recursively subdividing the buckets into smaller groups based on the remaining digits. You might want to consider explicitly performing the MSD radix sort rather than building the trie, since tries can be memory-inefficient when the data are sparse, while MSD radix sort has reasonably good memory usage (especially if you implement everything implicitly).
In the example you gave above, all of the numbers in the tuples were single digits. If this is the case, you can have at most 10 × 10 × 10 = 1000 possible distinct tuples, which isn't very large. In that case, you might want to consider just using a standard sorting algorithm with a custom comparator, since the benefits of a more optimized sort probably won't be all that apparent at that scale. On the other hand, if your tuples have many more entries in them, then it might be worth investing in a more clever sort, like MSD radix sort.
Hope this helps!