3 ms·
That sounds suspiciously like an insert sort. http://en.wikipedia.org/wiki/Insertion_sort http://en.wikipedia.org/wiki/Insertion_sort
by simcop2387 13y ago
That sounds suspiciously like an insert sort.
http://en.wikipedia.org/wiki/Insertion_sort http://en.wikipedia.org/wiki/Insertion_sort
- gizmo686 13y agoSimilar but asymptotically different. In insertion sort, if your partialy sorted list is [1,5], and the next element to insert is a two, you would scan the list until you arrive at the five, which. In the system I described the partialy sorted list would be represented as [1,_,_,_,5], and you would update the second element so it would be [1,2,_,_,5]. EDIT: After thinking about it, you could do the insertion step in O(1) time if you use a linked list instead of an array. The part where insertion sort gets its log(n) factor is in scanning the list, which can take (on average) no less than log(n) time. tantalor is correct in identifying this algorithm as pigeonhole sort.