2
$\begingroup$

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.

| improve this question | | | | |
$\endgroup$
1
$\begingroup$ 
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.

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Cool! This is probably exactly what I was looking for. $\endgroup$ – mavzolej Nov 2 '18 at 23:50
2
$\begingroup$ 
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]
| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ "How come I did not come up with this..." $\endgroup$ – mavzolej Nov 2 '18 at 22:37
  • $\begingroup$ @mavzolej: Sorry... THAT problem I simply cannot solve! $\endgroup$ – David G. Stork Nov 2 '18 at 22:42
  • $\begingroup$ 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$. $\endgroup$ – mavzolej Nov 2 '18 at 22:50
  • $\begingroup$ @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)$... $\endgroup$ – Henrik Schumacher Nov 3 '18 at 0:12
  • $\begingroup$ Sad news :) Thanks for telling though. $\endgroup$ – mavzolej Nov 3 '18 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.