Insertion Sort

In order to use INSERT instead of MERGE, we must divide L so that one of the pieces is a singleton.

divide L into its HEAD and its TAIL
recursively sort the TAIL
insert the HEAD into the sorted TAIL

Given L=[56,35,42,29]

HEAD=56 TAIL=[35,42,29]
sort TAIL:
- HEAD=35 TAIL=[42,29]
- sort TAIL:
  - HEAD=42 TAIL=[29]
  - TAIL already sorted
  - insert 42 in [29] Result=[29,42]
- insert 35 in [29,42] Result=[29,35,42]
insert 56 in [29,35,42] Result=[29,35,42,56]

Warning: although INSERT is a simpler operation than MERGE, Merge Sort is much more efficient than Insertion Sort.