On Thu, Dec 30, 2010 at 3:49 AM, Andreas Kostler <andreas.koestler.le...@gmail.com> wrote: > Isn't that the problem though? This will make the best case inefficient since > the work performed by into is proportional to the length of v2 (or v1 if you > swap them around). > Therefore, even thought the list is sorted you still need to traverse v2. A > simple fix would be > checking (= i 0) but that's kinda ugly.
No, v2 in your algorithm is only the portion you've scanned over to find the insertion (since you scan from the back). Your algorithm is fast for sorted lists, I checked. I think the only way you can beat that (using insertion sort) is if you have a data structure that allows for both a binary search to quickly find the insertion point, and then allows for fast insertion at that point. So maybe if finger trees can give you both the fast search and the fast insertion, that might pay off, but I still speculate it's unlikely to be any faster. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
