삽입정렬 in C#

 삽입 정렬의 경우 현재 항목의 앞부분이 정렬되어 있다면 아무런 연산을 하지 않는다. 따라서 삽입 정렬은 데이터 수 이외에도 입력된 데이터의 정리된 정도에 따라 수행속도에 차이가 나게 된다. 정렬되어 있는 데이터의 경우 데이터 수에 관계없이 수행 식간은 매우 짧다. 반면 역순의 경우는 i번째 항목은 무조건 i번의 자리 바꾸기를 하여야 하므로 선택 정렬에 비해 더 많은 시간을 소요하게 된다. 따라서 삽입 절렬은 거의 정리가 잘 되어 있는 데이터를 사용할 경우에 우수하다고 볼 수 있다. 삽입정렬의 복잡도는 선택 정렬과 마찬가지로 O(n^2)이며 데이터가 많아질수록 효율성이 급격히 떨어진다.