Merge Sort

From TRCCompSci - AQA Computer Science
Revision as of 10:45, 17 September 2018 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.

TRC PowerPoint

Merge Sort

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.


Merge Sort Example