What is merge sort?
• A sort that splits a list into halves
• Then merges them back in order
What type of approach does merge sort use?
• Divide and conquer
How does merge sort start?
• Split the list into smaller halves
When does merge sort stop splitting?
• When each sublist has one item
What happens after the splitting stage in merge sort?
• The sublists are merged back together in the correct order
What is an advantage of merge sort?
• Faster than simple sorts on large lists
What is a disadvantage of merge sort?
• Uses more memory
• More complex
What is insertion sort?
• A sort that takes each item and inserts it into the correct place in the sorted part on its left
How does insertion sort work?
• Start near the beginning
• Compare the current item with items to its left
• Insert it into the correct position
What is an advantage of insertion sort?
• Simple to understand
What is a disadvantage of insertion sort?
• Slow on large or badly ordered lists
