Sort algorithm to use for this specific scenario

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)

From stackoverflow

• 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
  

  rjohnston : I guess when I said "sorting" I meant "putting elements in order". The existing code does a sort because the lists aren't in order, I've just updated the DB to return them sorted correctly.