4
$\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 Answers 3

Reset to default
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$
4
  • $\begingroup$ Cool! This is probably exactly what I was looking for. $\endgroup$
    – mavzolej
    Nov 2, 2018 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$
    – SnzFor16Min
    Jun 24, 2020 at 5:59
  • 1
    $\begingroup$ Thank you @SneezeFor16Min. I removed the remark re timings. $\endgroup$
    – kglr
    Jun 24, 2020 at 6:31
  • $\begingroup$ This is actually slower in a list of say, 1 million elements, than just appending and sorting it, unfortunately ;) $\endgroup$
    – EGME
    Dec 12, 2021 at 15:44
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, 2018 at 22:37
  • 1
    $\begingroup$ @mavzolej: Sorry... THAT problem I simply cannot solve! $\endgroup$
    – David G. Stork
    Nov 2, 2018 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, 2018 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, 2018 at 0:12
  • $\begingroup$ Sad news :) Thanks for telling though. $\endgroup$
    – mavzolej
    Nov 3, 2018 at 0:20
1
$\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$
2
  • $\begingroup$ 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!! $\endgroup$
    – EGME
    Dec 12, 2021 at 15:55
  • $\begingroup$ 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. $\endgroup$
    – EGME
    Dec 12, 2021 at 17:36

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.