Timeline for What algorithm does sort use?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 30, 2014 at 8:48 | comment | added | jfbu |
Let B be initial already sorted list and A and C initially empty lists. Split B in two parts B1, B2 of lengths m and m or m+1 and m, compare newelt to first element of B2. If newelt is ≥ extend A to its right with B1 and replace B with B2, else extend C to its left with B2 and replace B with B1. After O(log n) such steps nothing is left in B. Then A contains the things ≤ newelt, and C those > newelt, and concatenation produces the extended sorted list. Apologies for not very e-lisp like language.
|
|
| Nov 23, 2014 at 13:02 | history | edited | Malabarba |
edited tags
|
|
| Nov 19, 2014 at 14:29 | comment | added | user227 | I'd use a binary heap (e.g. heap.el), if that was a frequent operation in my code. | |
| Nov 18, 2014 at 16:11 | vote | accept | Malabarba | ||
| Nov 18, 2014 at 15:56 | answer | added | legoscia | timeline score: 25 | |
| Nov 18, 2014 at 15:47 | history | asked | Malabarba | CC BY-SA 3.0 |