benchmarking is the only way to find that out.

I think a solution for maximum performance would look quite different and would be significantlyfaster (10x to 20x faster i would totally guess). Usually regular expressions are only faster if your programming language is not so performance (like early perl/php implementations I guess).

I feel bad for having cheated earlier, but I was desperate for an idea how to crack this quite difficult thing :(

I don't understand the last example:
[1, 2, 3] + [4, 5, 6] = [1, 2, 3, 4, 5, 6]

[1, 2, 4] + [1, 2, 3] = [1, 1, 2, 2, 3, 4]

[6, 5, 7] + [4, 3, 2] = [4, 3, 2, 6, 5, 7]

How is that last result made up? It says in the description that the result is to be sorted - but I don't see any valid sorting in concordance to the other two eamples.