작동 원리 : 인덱스를 증가시키며 현재 위치보다 이전의 값들을 비교한다. 인덱스 값이 인덱스 - 1 보다 큰동안 반복한다. 가장 코드가 간단하고 정렬할 데이터의 수가 적을 때 효율적인 코드이다.

시간복잡도 : O($n^2$)

• Required Function : swap

void swap(int *dest, int *src)
{
	int tmp;

	tmp = *dest;
	*dest = *src;
	*src = tmp;
}

C++, C

void insertion_sort(int* arr, int length)
{
	for (int i = 1; i < length; i++) 
		for (int j = i; j >= 0 && arr[j] < arr[j - 1]; j--) 
			swap((arr + j), (arr + j - 1));
}