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

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!"}}

x[[Ordering@x]] is much faster than Sort[x] for large lists.

• Cool! This is probably exactly what I was looking for. – mavzolej Nov 2 '18 at 23:50
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