# 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.

## 3 Answers

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. – mavzolej Nov 2 '18 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) – SneezeFor16Min Jun 24 '20 at 5:59
• Thank you @SneezeFor16Min. I removed the remark re timings. – kglr Jun 24 '20 at 6:31
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..." – mavzolej Nov 2 '18 at 22:37
• @mavzolej: Sorry... THAT problem I simply cannot solve! – David G. Stork Nov 2 '18 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$. – mavzolej Nov 2 '18 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)$... – Henrik Schumacher Nov 3 '18 at 0:12
• Sad news :) Thanks for telling though. – mavzolej Nov 3 '18 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[]]]

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"];