The merge sort is a sort where the operation of sorting is closely related to the process of merging. Let assume that there are two arrays that can be combined to produce a single sorted array. This process can be accomplished easily by successively selecting the record with the smallest key occurring in either of the tables and placing this record in a new table, thereby creating an ordered list.

Pass:

Initially the elements of the array are:

Table 1: 11 23 42
Table 2: 9 25

Table 1: 11 23 42
Table 2: 25

New Table: 9

Table 1: 23 42
Table 2: 25

New Table: 9 11

Table 1: 42
Table 2: 25

New Table: 9 11 23

Table 1: 42
Table 2:

New Table: 9 11 23 25

Table 1:
Table 2:

New Table: 9 11 23 25 42