License Creative Commons Attribution Share Alike 3.0-US
Keywords
insertion sort (1)
Permissions
Viewable by Everyone
Editable by All Siafoo Users
Hide
Bored? Check out the Recent Activity on Siafoo Join Siafoo Now or Learn More

Insertion Sort Atom Feed 3

In Brief Insertion Sort is a blissfully simple algorithm that is painfully inefficient for large arrays. It operates in place and with relative efficiency compared to several more complicated (read: better) algorithms in the case of extremely small arrays.... more
Performance Bound Cubic
Implementation Difficulty * * * * *
 1 function insertionsort(array)
2
3 len = length(array)
4
5 // If the array is empty, or contains only one element, it is already sorted
6 if len <= 1
7 return array
8
9 // Iterate through the array, starting with the second item
10 for i = 1 to i = len-1
11
12 // The current value for insertion
13 value = array[i]
14 j = i - 1
15
16 // Sift through preceding items in the array, shifting them each to the right
17 // until you find a spot where the to-insert value is less than the value
18 // to the right (and thus greater than the value to the left)
19 while j >= 0 and array[j] > value
20 array[j + 1] = array[j]
21 j -= 1
22
23 array[j + 1] = value
24
25 return array

Insertion Sort is a blissfully simple algorithm that is painfully inefficient for large arrays. It operates in place and with relative efficiency compared to several more complicated (read: better) algorithms in the case of extremely small arrays.