Best Case : $\Omega(n)$

Average Case : $\Theta(n^2)$

Worst Case : $O(n^2)$

우리말로 삽입 정렬이라고 하는 Inserting Sort 알고리즘은 새로운 배열에 기존의 값을 한개씩 삽입해 가며 정렬하는 알고리즘이다.

INSERTION-SORT(A)
	for j<-2 to lenth[A]
		do key <- A[j]
			i<-j-1
			while i>0 and A[i]>key
				do A[i+1]<-A[i]
				i<-i-1
			A[i+1]<-key