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.