## Merge sorting

• The operation of sorting is closely related to the process of merging.
• Two ordered table can be merged to produce a single sorted table.
• This can be accomplished by successively selecting the record with the smallest key occurring in the either of the table and placing this record in a new table, thereby creating an ordered list.

Procedure SIMPLE_MERGE(K, FIRST, SECOND, THIRD).

Given two ordered subtables stored in a vector K with FIRST, SECOND, and THIRD as just described, this procedure performs a simple merge. TEMP is a temporary vector used in the merging process. The variables I and J denote the cursor associated with the first and second subtables, respectively. L is an index variable associated with the vector TEMP.

K – Vector array to be sorted

FIRST – Starting index of the first array

SECOND – Starting index of the second array

THIRD – Ending index of the second array

TEMP – Temporary vector

I, J, L – Index variable

1)    [Initialize]

I <- FIRST

J <-SECOND

L <-0

2)    [Compare corresponding elements and output the smallest]

Repeat while I < SECOND and J<= THIRD

If K[I] <= K[J]

then    L <-L + 1

TEMP[L] <- K[I]

I <-I + 1

else     L<- L + 1

TEMP[L] ß K[J]

J<- J + 1

3)    [Copy remaining unprocessed elements in output area]

If I >= SECOND

then Repeat while J<= THIRD

L <- L + 1

TEMP[L] <- K[J]

J<- J + 1

else     Repeat while I < SECOND

L ß L + 1

TEMP[L] <-K[I]

I ß I + 1

4)    [Copy element in temporary vector into original area]

Repeat for I = 1, 2, …., L

K[FIRST  –1 + I ] ß TEMP[I]

5)    [Finished]

Return

### Example:

T1                    11        23        42

T2                    9          25

Trace:

T1                    11        23        42

T2                    25

NT                   9

T1                    23        42

T2                    25

NT                   9          11

T1                    42

T2                    25

NT                   9          11        23

T1                    42

T2

NT                   9          11        23        25

T1

T2

NT                   9          11        23        25        42