3
$\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
3
$\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!"}}

Improve this answer
$\endgroup$
3
  • $\begingroup$ Cool! This is probably exactly what I was looking for. $\endgroup$ – mavzolej Nov 2 '18 at 23:50
  • $\begingroup$ 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) $\endgroup$ – SneezeFor16Min Jun 24 '20 at 5:59
  • 1
    $\begingroup$ Thank you @SneezeFor16Min. I removed the remark re timings. $\endgroup$ – kglr Jun 24 '20 at 6:31
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$
6
  • $\begingroup$ "How come I did not come up with this..." $\endgroup$ – mavzolej Nov 2 '18 at 22:37
  • 1
    $\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
0
$\begingroup$

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"];
Improve this answer
$\endgroup$

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.