Basic Sorting and Searching Algorithms for Arrays, at a glance
Insertion sort uses linear search to find the location of the 1st element in the unsorted list, in the sorted portion of the list. It is an elementary sorting algorithm best used to sort small data sets or insert a new element in the sorted list.
Insertion sort starts with a sorted list of size 1 and inserts elements one at a time. It continues inserting each successive element into the sorted list so far.
1. Suppose if the array is sorted till index i then we can sort the array till i+1 by inserting the (i+1)th element in the correct position from 0 to i+1.
2. The position at which (i+1)th element has to be inserted has to be found by iterating from 0 to i.
3. As any array is sorted till 0th position (Single element is always sorted) and we know how to expand, we can sort the whole array.
To check out a Java Applet Visualization of Insertion Sort, click on the image below :
1. Best case performance – When the array is already sorted O(n). Total number of comparisons: N – 1 and total number of exchanges: N – 1.
2. Worst case performance – When the array is sorted in reverse order O(n2). N-1 iterations of comparison and exchanges.
3. Average case performance – O(n2)
4. It is sensitive to the input as the number of comparison and exchanges depends on the input.
5. It does not require any extra space for sorting, hence O(1) extra space.
Related Tutorials :
Tutorials on Sorting- at a glance
Computer Science >