License Creative Commons Attribution Share Alike 3.0-US
Keywords
insertion sort (1)
Permissions
Viewable by Everyone
Editable by All Siafoo Users
Hide
Don't get spied on – We respect your privacy and provide numerous options to protect it. 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.