sorting

Summary

Concept

Insertion sort

• sort tail recursively, insert head into sorted tail

Selection sort

• remove the smallest, sort the rest recursively

Merge sort

• split in half, sort each half recursively

Quick sort

• choose a random pivot, split into values larger and smaller than pivot, sort each set recursively