Sort Algorithm KO

Merge sort

________ is a recursive function, that calls itself.

Pairs of sublists

________ are combined into an ordered list containing all items in the two sublists.

Merge Sort Merge sort

________ is a type of divide and conquer algorithm.

Example Sort the following sequence in ascending order using bubble sort

5,3,4,1,2

Compare 5 and 3

swap

Compare 5 and 4

swap

Compare 5 and 1

swap

Compare 5 and 2

swap; end of pass 1

Compare 3 and 4

no swap

Compare 4 and 1

swap

Compare 4 and 2

swap

Compare 4 and 5

no swap; end of pass 2

Compare 3 and 1

swap

Compare 3 and 2

swap

Compare 3 and 4

no swap

Compare 4 and 5

no swap; end of pass 3

There are two steps

divide and combine Merge sort works by dividing the unsorted list sublists

Step 1

Divide

Keep dividing until there is only 1 item in each list Step2

Combine

What are the two kinds of sorting algorithms?

Merge sort and Bubble sort

What is the purpose of a sorting algorithm?

The purpose of sorting algorithms is to order an unordered list.
Item can be ordered alphabetically or by number.

Summarise the bubble sort algorithm

• Bubble sort steps through a list and compares pairs of adjacent
numbers.The numbers are swapped if they are in the wrong
order. For an ascending list if the left number is bigger than the
right number the items are swapped otherwise the numbers are
not swapped.
• The algorithm repeatedly passes through the list until no more swaps are needed.

Summarise the merge sort algorithm

• Merge sort is a type of divide and conquer algorithm.
• There are two steps: divide and combine
• Merge sort works by dividing the unsorted list sublists. It
does this until there is 1 item in each list.
• Pairs of sublists are combined into an ordered list. The algorithm continues until there is only 1 ordered list remaining.

What is the advantage of a bubble sort? (1)

It is a very simple and robust algorithm

What is the disadvantage of a bubble sort?

Can be slow particularly for long lists. As the number of items increases the time taken for the algorithm to run increases.

What is the advantage of a merge sort?

Much faster than bubble sort especially when the number of elements are large.

What is the disadvantage of a merge sort?

It is a bit more complex to understand
Step 1: Divide
Step 2: Combine

merge sort

bubble sort