On 30/12/2010, at 8:54 PM, Mark Engelberg wrote: > 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. Oh of course. I apologise. Mark do you mind to lay out how you perform your benchmarks. On my system (insertion-sort (into [] (range 10000))) runs for an unacceptable amount of time (talking ~10s) That seems to be quite long for sorting an already sorted vector of 10k elements.
> 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. With the initial implementation, using binary search to find the insertion point should still result in a speed up, right? > > -- > 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 -- 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
