Insertion Sort

A sorting algorithm in which every item will be implemented a time. The first item that will be implemented is the first item in the list.

Algorithm:
The list will be devided imaginarilly by into sorted list and unsorted list. The algorithm will take the first element of the unsorted list and insert it to right place in the sorted list in every step. if there will be no item in unsorted list, the algorithm stop.

PseudoCode(C++):

void insertionSort(int arr[], int length) {
      int i, j, tmp;
      for (i = 1; i < length; i++) {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                  tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
                  j--;
            }
      }
}


Source:
http://en.wikipedia.org/wiki/Insertion_sort
http://www.algolist.net/Algorithms/Sorting/Insertion_sort