Instead of merging one by one ( total), divide the lists in half and merge pairwise.
Split lists into two groups of .
Recursively merge each group.
Merge the two resulting lists.
This gives where is total elements. Each element is touched times across all merge levels.