Merge sort is an efficient, general-purpose, comparison-based sorting algorithm.
Course: Software Foundations, Spring 2020
Taught by: Prof. Venkatesh Chopella
Merge sort is modeled as a transition system in various stages.
- Manual Swap
- Manual Order
- Manual Order, Manual Merge
- Automatic Order, Manual Merge
- Automatic Order, Automatic Merge
Stage 5 is the actual merge sort algorithm, which is obviously automatic (the computer does it for you). The idea is to see the merge sort algorithm as a system derived from the very simple Manual Swap system. Proofs of each such system are taught in the course.