Difference between revisions of "Merge Sort"
| Line 6: | Line 6: | ||
https://www.youtube.com/watch?v=RBM_GabALOM&index=8&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E | https://www.youtube.com/watch?v=RBM_GabALOM&index=8&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E | ||
| + | |||
| + | ===TRC PowerPoint=== | ||
| + | [https://studentthomrothac-my.sharepoint.com/:p:/g/personal/wayne_jones_thomroth_ac_uk/Ee59IigjmXJHnpYOFq51VVoBBg2ndz2yT4fWu4IgQtHeeg?e=kWz9Pj Merge Sort] | ||
==Stage 1== | ==Stage 1== | ||
Revision as of 10:45, 17 September 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
Contents
TRC PowerPoint
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
