MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Insertion into sorted list

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

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]},
                  e]]; \[IndentingNewLine]If[
                p[e, lst\[LeftDoubleBracket]
                    mid\[RightDoubleBracket]], \[IndentingNewLine]upper
                  mid, \[IndentingNewLine]lower =
                  mid + 1\[IndentingNewLine]];\[IndentingNewLine]];\)\
\[IndentingNewLine]]; \[IndentingNewLine]Insert[lst, e,

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?


On Nov 6, 6:59 pm, "Andrew Moylan" <andrew.j.moy... at> 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

  • Prev by Date: RE: really simple question
  • Next by Date: Re: Insertion into sorted list
  • Previous by thread: Re: Insertion into sorted list
  • Next by thread: Re: Insertion into sorted list