�鶹������ҳ���

A merge sort is a more complex sort, but also a highly efficient one.

A merge sort uses a technique called divide and conquer. The list is repeatedly divided into two until all the elements are separated individually. Pairs of elements are then compared, placed into order and combined. The process is then repeated until the list is recompiled as a whole.

Consider this unsorted list:

The list is split into half:

The process repeats:

Until all elements are individually separated:

The algorithm looks at the individual elements and compares them as pairs. Each pair is sorted into order:

The pairs are then compared, starting with the first number in each pair. If the left hand number is smaller than the right hand number, it is placed in order. The comparison then moves up to the second number on the left hand side and the process repeats. If the right hand number is smaller, it is placed in order and the comparison moves to the next number on that side.

Here, 7 is the first left hand number and 5 is the first right hand number. 7 is bigger than 5, so 5 is placed in order:

5

The next right hand number is 10. 7 is smaller than 10, so 7 is placed in order:

5   7

The next left hand number is 11. 11 is bigger than 10, so 10 is placed in order:

5   7   10

There are no more right hand numbers to compare, so the remaining left hand numbers are placed in order:

5   7   10   11

The process is repeated for the initial right hand division:

Eventually the list is recompiled

The list is now sorted into the correct order.