Use induction to prove that insertion sort 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 element into the sorted array.

Solution

In insertion we have two parts of the an array, sorted and the unsorted part. We take one number at once from the unsorted array and place it in the correct position in the sorted part. We start from the beginning and initially the whole array is in unsorted and sorted is just nil. We find the position in the sorted array by comparing with each number in sorted from the beginning and when we find the number which is greater than this number, we insert the number before that number. So if the numbers are same, then they will be in the same order even after sorting.

Let n be the number of numbers in the array to be sorted.

If n = 1, the array is sorted. Insertion sort will not change anything so it is stable.

Let us assume insertion sort is stable until n=k.

When n = k+1, let us first use incersion sort to sort first k numbers. This will be stable. Now are left with only one number. Based on the above explanation this will not disturb the stability. Hence it is also for n = k+1.

Hence proved.