Algorithms and data structures · Introductory

Merge sort: combine already sorted sequences

Derive the worst-case bound from splitting and merging, and see how equality handling controls stability.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Split first, then restore sorted order by merging
  2. Merge two concrete sequences
  3. Add the work across recursion levels
  4. Use stability and sequential processing deliberately
  5. Ask Logeia about this articleCheck your understanding

Split first, then restore sorted order by merging

Merge sort divides a sequence into two parts, sorts each part, and combines the sorted results. A sequence of zero or one element is already sorted. To merge two sorted sequences, compare their next unused elements, output the smaller one, and advance only that sequence. When one sequence is exhausted, append the remaining elements of the other. Splitting alone does not sort the data: the merge step is what restores the sorted-order condition at each level of the divide-and-conquer structure.

Merge two concrete sequences

Merge [1, 4, 8] with [2, 4, 7]. Compare one with two and output one, then compare four with two and output two. The next candidates are both four. To preserve the original relative order of equal keys, choose the one from the left sequence first. Continue with the other four, seven, and eight, obtaining [1, 2, 4, 4, 7, 8]. Each element is output once, making a merge of lengths a and b linear in a + b. Expensive key extraction or comparison adds its own cost.

Add the work across recursion levels

Splitting roughly in half creates logarithmically many levels. At a fixed level, the lengths of all sequences being merged sum to n, so that level performs linear total work. Combining these facts yields O(n log n) worst-case time for standard merge sort. A conventional array implementation uses an auxiliary destination array of O(n) space, in addition to recursion bookkeeping. Do not claim constant auxiliary space for every implementation. Lists, bottom-up iteration, and specialized in-place variants have different implementation trade-offs even though they share the broad merging idea.

Use stability and sequential processing deliberately

Stability means preserving the relative input order of items whose sorting keys compare equal. Merge sort can be stable when the merge rule takes the left item first on a tie, assuming the recursive results are themselves stable. This permits ordered passes over different keys, such as preserving date order within equal employee names. Merging also consumes and produces sequences in order, which is useful for external sorting: create sorted runs that fit in memory and then merge their files. The available memory and number of runs determine practical buffering and I/O choices.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path