A stable sort is a sorting algorithm that, when there are duplicate keys, always keeps the order of the duplicates intact when it sorts the data. Quicksort is famous for not being a stable sort (because of the way partition swaps records); Merge Sort, however, is a stable sort. Use induction to prove that insertion sort is a stable sort. The base case is the starting state of the array; the inductive step should discuss what happens when we insert a single new clement into the sorted array