‘Split data until each item is in a list of its own and then combine pairs of lists repeatedly so that the items are in order.’

‘Move through a list repeatedly, comparing items next to each other and swapping them if they are in the wrong order.’

Analyse the flow chart below. Which algorithm does this represent?

What does the initial value of -1 indicate?

Which sort splits data repeatedly until each item is in a list of its own

Which sort  creates a new list each time two lists are combined

An advantage of merge sort over bubble sort is that it is faster to sort large lists and lists that are less ordered.

Bubble sort can be quicker than merge sort on smaller lists and lists that are mostly in order.

Key Stage 4

Algorithms review

'The merge sort algorithm has two parts: splitting items and merging items'

The first part of a merge sort it to repeatedly split a list in half until all the elements are in a list by themselves.

Each stage of the merge sort algorithm can be shown in two parts: splitting the items and merging pairs of lists.

The merge sort algorithm is less complex to implement than bubble sort.

The advantage to merge sort is that it requires more memory, often due to the new lists that need to be created.

"Executing a merge sort takes up extra space in memory, as new lists are made each time a list is split or two lists are combined."

"A merge sort algorithm is usually slower to execute but more easier to write than bubble sort."

"Merge sort is an efficient divide and conquer algorithm that can perform well in real-world use."