24 compares, including line 35 (edited). n + m instead of n * m!

The real difference will come if you work with large data.

Say both lists have 1.000 elements.

Originally that would be 1.000.000 compares.

But:

sort (1000 * 10 {= log2 1000}): 10000

sort (1000 * 10 {= log2 1000}): 10000

1000+1000 = 2000

altogether: 22.000

That is a lot less. It is approx 1/40

(ever if one compare may now take a bit longer)

and double the size of both lists:

Originally that would be 4.000.000 compares.

Sorted takes 48.000

approx 1/80

And that is based on the sorting worst case. Many sorting methods will have a worst case of O(n log n), but average at an even better level.