General Sorting Strategy

A sorting algorithm takes as input any list and outputs a list that is sorted and has the same elements as the input list.

Given a list L:

if L has 0 or 1 element: it is already sorted
otherwise:
- divide L into L1 and L2
- recursively sort L1 and L2, producing L1' and L2'
- combine L1' and L2' producing L'

How to combine L1' and L2'?

Unique way: MERGE

This strategy works no matter how we divide L, as long as neither L1 nor L2 is empty.

Different methods for dividing L result in different sorting algorithms: Merge Sort, Insertion Sort, Quick Sort.