# Inserting an integer into a sorted list

I'm wondering if inserting an integer into a sorted list (in a way that the list remains sorted) can be performed in Mathematica in some fancy way in $$\log(N)$$ time?..

The question was asked here, but I'm not sure if any of realizations presented there work in $$\log(N)$$. I would appreciate if anyone provided the solution for not simply a list, but for a list of lists sorted by their certain element. E.g.:

ins[{{1,b},{3,{}},{14,"hi!"}},{6,0}]


gives:

{{1,b},{3,{}},{6,0},{14,"hi!"}}


Where sorting was performed by the first field of the sublist.

• Of course, one could implement a binary tree... Commented Nov 2, 2018 at 22:03

ClearAll[insertAndSort]
insertAndSort = With[{a = Join[#, {#2}]}, a[[Ordering[a[[All, 1]]]]]] &;


Example:

a = {{1, c}, {3, {}}, {14, "hi!"}};
b = {6, 0};
insertAndSort[a, b]


{{1, c}, {3, {}}, {6, 0}, {14, "hi!"}}

• Cool! This is probably exactly what I was looking for. Commented Nov 2, 2018 at 23:50
• Note: x[[Ordering@x]] isn't necessarily faster than Sort[x] for large lists. Small test: With x=RandomReal[10, 100000], average timing for 10k cycles: x[[Ordering@x]] = 7.76ms; Sort[x] = 4.32ms (on v12.1) Commented Jun 24, 2020 at 5:59
• Thank you @SneezeFor16Min. I removed the remark re timings.
– kglr
Commented Jun 24, 2020 at 6:31
• This is actually slower in a list of say, 1 million elements, than just appending and sorting it, unfortunately ;)
– EGME
Commented Dec 12, 2021 at 15:44
myList = {{1, b}, {3, {}}, {14, "hi!"}};
myElement = {6, 0};
SortBy[Join[myList, {myElement}], First]


or

myList = {{1, b}, {3, {}}, {14, "hi!"}};
myElement = {6, 0};
SortBy[Insert[myList, myElement, 1], First]

• "How come I did not come up with this..." Commented Nov 2, 2018 at 22:37
• @mavzolej: Sorry... THAT problem I simply cannot solve! Commented Nov 2, 2018 at 22:42
• I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $N\log N$ time, while for a single unsorted element it should be able to work in $\log N$. Commented Nov 2, 2018 at 22:50
• @mavzolej While Sort and Ordering themselves will might have complexity below $O(N)$, Join will have to make a copy of the full old list, so it has complexity $O(N)$... Commented Nov 3, 2018 at 0:12
• Sad news :) Thanks for telling though. Commented Nov 3, 2018 at 0:20

As it is known that your input list is sorted we could do this with a binary search. As of Mathematica 10.1 I am not aware of a fast built-in for this operation so I shall use Leonid's code.

ins[s_List, x_] := Insert[s, x, bsearchMax[s[[All, 1]], x[[1]]]]

ins[{{1, b}, {3, {}}, {14, "hi!"}}, {6, 0}]

{{1, b}, {3, {}}, {6, 0}, {14, "hi!"}}


Leonid's code needed for the function above:

bsearchMax =
Compile[{{list, _Real, 1}, {elem, _Real}},
Block[{n0 = 1, n1 = Length[list], m = 0}, While[n0 <= n1, m = Floor[(n0 + n1)/2];
If[list[[m]] == elem, While[m >= n0 && list[[m]] == elem, m--]; Return[m + 1]];
If[list[[m]] < elem, n0 = m + 1, n1 = m - 1]];
If[list[[m]] > elem, m, m + 1]], RuntimeAttributes -> {Listable},
CompilationTarget -> "C"];

• Hello, we meet again! I am surprised there is no in built function to do this very fundamental operation fast, as is many times needed. Would you be able to update your version of bsearchMax to work with the newer and coming FunctionCompile … I am not sure I know how to do it???!!! I am not very familiar with Compile, and was looking also for a fast way to do this … I am investigating CA numbers beyond the 10^7-th if possible, but I can’t even get to 10^6 with what I have now. I thank you in advance if possible!!
– EGME
Commented Dec 12, 2021 at 15:55
• So, if you use this, with reasonably large lists, it is at least twice as slow as just sorting the list … unfortunately … something better is needed, but I don’t know what that could be.
– EGME
Commented Dec 12, 2021 at 17:36

1. Introduction

Since V 12.1 there is CreateDataStructure

A link to its many members: DataStructures

A suitable choice for the question at hand would be SortedMultiset

Look under documentation details to see that it works in O(log n).

what-does-olog-n-mean-exactly?

2. Question at hand

a = {{1, c}, {3, {}}, {14, "hi!"}};
b = {6, 0};

ds = CreateDataStructure["SortedMultiset"];

ds["Insert", #] & /@ a;
ds["Insert", {6, 0}];

ds["Elements"]


{{1, c}, {3, {}}, {6, 0}, {14, "hi!"}}

3. Another example for better visualization

ds = CreateDataStructure["SortedMultiset"];

ds["Insert", #] & /@ Range[1, 30, 2];

ds["Visualization"]


ds["Insert", 24];

Normal @ ds


{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 24, 25, 27, 29}

We can insert the same value several times:

ds["Insert", 24]

Normal @ ds


{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 24, 24, 25, 27, 29}

Delete one instance of 24:

ds["Delete", 24] // Normal


{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 24, 25, 27, 29}

Delete all instances of 24:

ds["DeleteCases", 24] // Normal


{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}