Merge Sort

Procedure Mergesort (A, start, finish)

The above Procedure Subalgorithm recursively sorts given list of elements between position “start’ and “finish” (inclusive) . Array ‘A’ contains ‘n’ number of elements. Variables ‘length’ and ‘mid’ refer to the number of elements in the current sublist and position of the middle element of the sublist, respectively.

Step 1 Computation, size of current sublist

set length ¬ finish – start + 1

Step 2 Condition checking, if length is one

if (length £ 1) then

return

Step 3 calculating, middle point

set mid ¬ sort + élength/2ù – 1

Step 4 solving I sublist, recursively

call Mergesort (A, start, mid)

Step 5 Solving II sublist, recursively

call Mergesort (A, mid + 1, finish)

Step 6 Merging two sublists, sorted

call Merge (A, start, mid + 1, finish)

Step 7 Finish

return

Procedure Merge (A, first, second, third)

The above procedure subalgorithm merges the two lists and produces a new sorted list. Temporary array 'temp' is used for holding sorted values.

Step 1 initialisation

set n ¬ 0, f ¬ first, S ¬ second

Step 2 Comparison, giving smallest element

if (A[f] £ A[S]) then

set n ¬ n + 1

set temp [n] ¬ A[f]

set f ¬ f + 1

else

set n ¬ n + 1

set temp [n] ¬ A[S]

set S ¬ S + 1

Step 3 Copying remaining elements

if (f ³ second) then

loop

Repeat while (S £ third)

set n ¬ n + 1

set temp [n] ¬ A[S]

set S ¬ S + 1

End loop

else

loop

Repeat while (f <>

set n ¬ n + 1

set temp [n] ¬ A[S]

set f ¬ f + 1

End of loop

Step 4 Copying, element to original array

loop

Repeat for f ¬ 1, 2, ---- n

A [first – 1 + f] ¬ temp [f]

End of loop

Step 5 finish

return