Insertion Sort
def insertionSort(listOfVals):
current = 1
while (current < len(listOfVals)):
pivot = listOfVals[current]
underExam = current - 1
while ((underExam >= 0) and (listOfVals[underExam] > pivot)):
listOfVals[underExam+1] = listOfVals[underExam]
underExam = underExam - 1
listOfVals[underExam+1] = pivot
current = current + 1
return (listOfVals)
- What is the best case number of comparisons (inner While)? What type of list causes this?
- What is the worst case number of comparisons (inner While)? What type of list causes this?