Sort algorithm to use for this specific scenario

Question

I have two lists - let's call them details and totals.

The items in details have multiple elements for each key that the list is sorted on, as such:

KEY1
KEY1
KEY2
KEY2
KEY3
KEY3
KEY3
etc

The items in totals will only have each key once, as such:

KEY1
KEY2
KEY3
etc

Both lists are sorted by key already. The lists need to be combined so that the new list has the details elements followed by it's corresponding element from totals, as such:

KEY1 (this is from details)
KEY1 (this is from details)
KEY1 (this is from totals) etc

Which sorting algorithm will result in the best performance in this scenario?

(in all honesty, I'm just going to change the code so that the row from totals is created-and-inserted as the details list is being built, this is more of an academic question)

Answer 1

If you're looking at combining the two lists into one, and they're sorted already, you shouldn't be resorting.

A simple merge will do, as follows. This is assuming your assumptions are correct and there are no "naked" detail or total lines (details without totals or totals without details). If there are, you'll need extra code to handle that but the principle is the same.

Get first detail-list
Get first total-list

While total-list not finished:
    If detail-list.key > total-list.key:
        Output total-list
        Get next total-list
        Next while
    Output detail-list
    Get next detail-list