Insertion Sort

#Sorting#Computer-Science#CS251 Does an ordered insertion of each element into a sorted subarray. Imagine how you would sort Uno cards in your hand. You would have a sorted/unsorted part and slowly add cards to the sorted section.

Pseudocode §

InsertionSort(A: array of size n)
	for (i = 1, i < n, 1)
		j <- i-1
		while (j >= 0 and A[j] > A[j+1])
			swap(A, j, j+1)
			j <- j-1
		end while
	end for
end InsertionSort

Details §

• Is stable and in place
• If array is sorted, $\in \Theta (n)$
• If array is sorted in opposite order, $\in \Theta (n^2)$

Best Case $\in \Theta (n)$ §

Worst Case $\in \Theta (n^2)$ §