Sorting and searching are two of the most frequently needed algorithms in program design. Standard algorithms have evolved to take account of this need.
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 algorithmA sequence of logical instructions for carrying out a task. In computing, algorithms are needed to design computer programs. 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: