Jabarkan merge( input_tape, output_tape, scratch_tape_C) dari Urut gabung

while any records remain on C or D

# take the next sorted chunk from the input tapes, and merge into the single given output_tape.

# tapes are scanned linearly.

# tape[next] gives the record currently under the read head of that tape.

# tape[current] gives the record previously under the read head of that tape.

# (Generally both tape[current] and tape[previous] are buffered in RAM ...)

read next record from left tape

read next record from right tape

while left[current] < left[next] and right[current] < right[next]

Contoh penerapan atas sebuah larik sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:

Larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}

Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}

Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut {1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah dipindahkan ke larik baru)

langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya.

{1, 2} <-> {3, 4, 9} dan {5}

{1, 2, 3} <-> {4, 9} dan {5}

{1, 2, 3, 4} <-> {9} dan {5}

{1, 2, 3, 4, 5} <-> {9} dan {null}

{1, 2, 3, 4, 5, 9} <-> {null} dan {null}