Merge Sort

Merge sort is an example of a divide and conquer algorithm.

It works by splitting all the items in a list into lists of length one, it then combines these in order.

https://www.youtube.com/watch?v=RBM_GabALOM&index=8&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E

Stage 1

The list of values is split in two. This is repeated until every item is in its own list.

Stage 2

Then the adjacent lists are merged. This is done by comparing the first item of each list. The lowest value is placed into the new list and removed from the old list. this is repeated until all the values from the two lists have been moved into the new list.

This is repeated until you have a single list again.

Example