Re: Insertion into sorted list

*To*: mathgroup at smc.vnet.net*Subject*: [mg71103] Re: Insertion into sorted list*From*: "Andrew Moylan" <andrew.j.moylan at gmail.com>*Date*: Wed, 8 Nov 2006 06:15:49 -0500 (EST)*References*: <eimq10$9b7$1@smc.vnet.net>

Thanks for your replies. I've written a function 'InsertSorted' that solves this problem using a binary search. Here's the usage string: InsertSorted::usage = "InsertSorted[l, e] gives the sorted List l with e inserted such that the resulting List is \ also sorted. InsertSorted[l, e, p] uses the ordering function p."; And here's the function definition, which can be pasted into a new cell in a Mathematica notebook: \!\(\(InsertSorted[lst_List, e_, p_: \((OrderedQ[{#1, #2}] &)\)] := Module[\[IndentingNewLine]{lower = 1, upper = Length[lst] + 1}, \[IndentingNewLine]While[ lower \[NotEqual] upper, \[IndentingNewLine]\(With[{mid = Floor[\(lower + upper\)\/2]}, \[IndentingNewLine]Print[ p[lst\[LeftDoubleBracket]mid\[RightDoubleBracket], e]]; \[IndentingNewLine]If[ p[e, lst\[LeftDoubleBracket] mid\[RightDoubleBracket]], \[IndentingNewLine]upper = mid, \[IndentingNewLine]lower = mid + 1\[IndentingNewLine]];\[IndentingNewLine]];\)\ \[IndentingNewLine]]; \[IndentingNewLine]Insert[lst, e, lower]\[IndentingNewLine]];\)\) I'm sorry to dsitribute the function in this slightly messy way. I also have a notebook and associated automatically-generated .m file, which represent a package "InsertSorted`" that can be placed in Mathematica/Applications as usual and accessed via the Needs function. Can anyone suggest the "correct" way to distribute such packages to any users of this newsgroup who might be interested? Cheers, Andrew On Nov 6, 6:59 pm, "Andrew Moylan" <andrew.j.moy... at gmail.com> wrote: > Hi all, > > I have a sorted List. I need to occasionally insert new elements, while > always keeping the list sorted. Is there a more efficient way to do > this than the most obvious way (calling Append then calling Sort)? > > Thanks for any help, > > Andrew