>>11491779>>11491765I believe it’s in place insertion sort. Instead of bubbling everything to the top, this makes a sorted sublist on the left side of the array and slowly increases size. Since the subarray is sorted, when appending a new element, it suffices to swap until element isn’t swappable with any more elements of the original sorted subarray - the relative order of the sorted elements is preserved, and the swapping process has now sorted the new element into its place (I’m being a bit handwavy here but I’m sure you can see how this works).
>>11491851Uh, not sure how sophisticated an argument your instructor is asking for, but here is the worst case input: consider an array in descending order (ie greatest to least). Then the initial sorted sublist, which is a single element, is the greatest element in the array. Then we append next element in the array, which is the second greatest element, to the sorted sublist on the left. It’s less than the greatest element, so we swap and have a sorted array of the 2 greatest elements. Continuing inductively in this fashion, on step k, we have a sorted sublist of the greatest (k - 1) elements on the left, and we will then sort the kth greatest element into that list. This necessarily means we perform (k - 1) swaps since the kth greatest element is the smallest element in a list of the k greatest elements. Hence, on the nth step, we will require (n - 1) swaps.
At each step, we do (k - 1) swaps here, and there are (n - 1) steps as we are iterating from 2 to n. We know k grows with n, so our approximate cost is . To see the bound is tight, we observe .
This is sort of a lazy argument, but I hope you see the idea.
