This article describes two sorting algorithms (gnome sort and bozosort) and gives their correctness proof in full detail.