Difference between revisions of "Merge Sort"
| Line 2: | Line 2: | ||
It works by splitting all the items in a list into lists of length one, it then combines these in order. | It works by splitting all the items in a list into lists of length one, it then combines these in order. | ||
| + | |||
| + | <youtube>https://www.youtube.com/watch?v=RBM_GabALOM&index=8&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E</youtube> | ||
| + | |||
| + | https://www.youtube.com/watch?v=RBM_GabALOM&index=8&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E | ||
==Stage 1== | ==Stage 1== | ||
Revision as of 11:40, 11 June 2018
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
