Merge Sort - Lakelands Computing

Merge Sort Algorithm

All sorting algorithms take a list of data (numbers, letters) and sort it into either ascending order with smallest number first and biggest number last or descending order (biggest number first).

Merge sort works by splitting a list down into sections then taking the smallest value from each of those sections and comparing it to make a new "sorted" section.

The only way you can be sure to be able to identify the smallest value in a section is to make each section have just 2 numbers in in.

It takes a couple of minutes to get your head around this one so lets go through an example (or watch the video at the bottom of the page - a live walkthrough is probably easier to make sense of.)

Starting (unsorted) list [ 9, 2 , 4, 6, 8 , 1 , 3 ,7]

Split list into two sections [ 9, 2 , 4, 6] and [ 8 , 1 , 3 ,7]

more than 2 items in each section so split it again

[ 9, 2 ] and [4, 6] and [ 8 , 1] and [3 ,7]

now compare each pair of numbers and put smallest one first (in its pair)

[ 2,9 ] and [4, 6] and [ 1,8] and [3 ,7]

Now we are ready to start building it back together

Take the first 2 pairs [ 2,9 ] and [4, 6] compare the first number in each pair (compare 2 to 4)

2 is smallest so it goes into out new section list

Now repeat that step - take what is left of first two pairs [ 9 ] and [4, 6] compare the first number in each pair (compare 9 to 4), 4 is smallest so it is next in our new section list

[2,4]

Now repeat that step - take what is left of first two pairs [ 9 ] and [ 6] compare the first number in each pair (compare 9 to 6 ), 6 is smallest so it is next in our new section list

[2,4,6]

Now repeat that step - take what is left of first two pairs [ 9] and [ ] compare the first number in each pair (only 9), so 9 is smallest so it is next in our new section list
- [2,4,6,9]

That is the first section rebuilt (using pairs 1 and 2)

Now redo the same using pairs 3 and 4 [ 1,8] and [3 ,7]

Compare the first numbers form each pair (1 and 3). 1 is smaller so it goes into our new section list

[1] etc etc

[1,3,7,8]

Now take the two rebuilt sections lists [2,4,6,9] and [1,3,7,8] and compare the first 2 items (1 and 2). 1 is smallest so goes into our merged list

Repeat the process comparing the first numbers of each section until you have merged both lists

[1,2,3,4,6,7,8,9]