The costliest merge

Merge sort's merge step combines two already-sorted lists by repeatedly comparing their front elements, emitting the smaller, and - once one list is exhausted - copying the remainder of the other with no further comparisons. You must merge two sorted lists of four elements each (eight distinct values total). Over all possible ways the eight values could be split between the two lists, what is the maximum number of front-to-front comparisons a single merge can make?

Show hints (2)+
  1. A merge stops comparing as soon as one list is empty; the other's tail is copied for free.
  2. The last element placed never costs a comparison, so the ceiling is m+n−1m+n-1 - is it reachable?

Answer

Reveal answer →

7

Create a free account to see the full worked solution and track your progress.

Interview format: Trading Aptitude Tests, Prop Trading

Related questions