Difference between revisions of "Merge Sort"
| (2 intermediate revisions by the same user not shown) | |||
| 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 | ||
| + | |||
| + | ===TRC PowerPoint=== | ||
| + | [https://studentthomrothac-my.sharepoint.com/:p:/g/personal/wayne_jones_thomroth_ac_uk/Ee59IigjmXJHnpYOFq51VVoBBg2ndz2yT4fWu4IgQtHeeg?e=kWz9Pj Merge Sort] | ||
==Stage 1== | ==Stage 1== | ||
| Line 11: | Line 18: | ||
This is repeated until you have a single list again. | This is repeated until you have a single list again. | ||
| + | ==Example== | ||
[[File:Merge sort.gif|Merge Sort Example]] | [[File:Merge sort.gif|Merge Sort Example]] | ||
Revision as of 11: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
