Insertion Sort?

• 단순한 정렬 알고리즘
• 정렬된 Array를 유지하며 진행함.
• 새로운 숫자가 삽입되면 정렬된 Array 내부에서 자기 자리를 찾아가며 정렬됨.

Code

void insertionSort(int n, keytype S[])
{
	index i, j;
	keytype x;
	
	for(i=1; i<n; i++){
		x = S[i];
		j = i - 1;
		while(j>=0 && S[j] > x) {
			S[j+1] = S[j];
			j--;
		}
		S[j+1] = x;
	}
}  

Time Complexity

• Worst : $O(n^2)$
• Average : $O(n^2)$
• Best : $O(n)$