Inserting an integer into a sorted list

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
2
down vote

favorite












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.










share|improve this question

















  • 1




    Of course, one could implement a binary tree...
    – Henrik Schumacher
    1 hour ago















up vote
2
down vote

favorite












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.










share|improve this question

















  • 1




    Of course, one could implement a binary tree...
    – Henrik Schumacher
    1 hour ago













up vote
2
down vote

favorite









up vote
2
down vote

favorite











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.










share|improve this question













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.







list-manipulation sorting






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 2 hours ago









mavzolej

35819




35819







  • 1




    Of course, one could implement a binary tree...
    – Henrik Schumacher
    1 hour ago













  • 1




    Of course, one could implement a binary tree...
    – Henrik Schumacher
    1 hour ago








1




1




Of course, one could implement a binary tree...
– Henrik Schumacher
1 hour ago





Of course, one could implement a binary tree...
– Henrik Schumacher
1 hour ago











2 Answers
2






active

oldest

votes

















up vote
1
down vote



accepted










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.






share|improve this answer






















  • Cool! This is probably exactly what I was looking for.
    – mavzolej
    5 mins ago

















up vote
2
down vote













myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]





share|improve this answer




















  • "How come I did not come up with this..."
    – mavzolej
    1 hour ago










  • @mavzolej: Sorry... THAT problem I simply cannot solve!
    – David G. Stork
    1 hour ago










  • I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
    – mavzolej
    1 hour ago











Your Answer





StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f185197%2finserting-an-integer-into-a-sorted-list%23new-answer', 'question_page');

);

Post as a guest






























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
1
down vote



accepted










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.






share|improve this answer






















  • Cool! This is probably exactly what I was looking for.
    – mavzolej
    5 mins ago














up vote
1
down vote



accepted










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.






share|improve this answer






















  • Cool! This is probably exactly what I was looking for.
    – mavzolej
    5 mins ago












up vote
1
down vote



accepted







up vote
1
down vote



accepted






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.






share|improve this answer














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.







share|improve this answer














share|improve this answer



share|improve this answer








edited 23 mins ago

























answered 38 mins ago









kglr

169k8192396




169k8192396











  • Cool! This is probably exactly what I was looking for.
    – mavzolej
    5 mins ago
















  • Cool! This is probably exactly what I was looking for.
    – mavzolej
    5 mins ago















Cool! This is probably exactly what I was looking for.
– mavzolej
5 mins ago




Cool! This is probably exactly what I was looking for.
– mavzolej
5 mins ago










up vote
2
down vote













myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]





share|improve this answer




















  • "How come I did not come up with this..."
    – mavzolej
    1 hour ago










  • @mavzolej: Sorry... THAT problem I simply cannot solve!
    – David G. Stork
    1 hour ago










  • I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
    – mavzolej
    1 hour ago















up vote
2
down vote













myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]





share|improve this answer




















  • "How come I did not come up with this..."
    – mavzolej
    1 hour ago










  • @mavzolej: Sorry... THAT problem I simply cannot solve!
    – David G. Stork
    1 hour ago










  • I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
    – mavzolej
    1 hour ago













up vote
2
down vote










up vote
2
down vote









myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]





share|improve this answer












myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]






share|improve this answer












share|improve this answer



share|improve this answer










answered 1 hour ago









David G. Stork

22k21747




22k21747











  • "How come I did not come up with this..."
    – mavzolej
    1 hour ago










  • @mavzolej: Sorry... THAT problem I simply cannot solve!
    – David G. Stork
    1 hour ago










  • I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
    – mavzolej
    1 hour ago

















  • "How come I did not come up with this..."
    – mavzolej
    1 hour ago










  • @mavzolej: Sorry... THAT problem I simply cannot solve!
    – David G. Stork
    1 hour ago










  • I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
    – mavzolej
    1 hour ago
















"How come I did not come up with this..."
– mavzolej
1 hour ago




"How come I did not come up with this..."
– mavzolej
1 hour ago












@mavzolej: Sorry... THAT problem I simply cannot solve!
– David G. Stork
1 hour ago




@mavzolej: Sorry... THAT problem I simply cannot solve!
– David G. Stork
1 hour ago












I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
– mavzolej
1 hour ago





I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
– mavzolej
1 hour ago


















 

draft saved


draft discarded















































 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f185197%2finserting-an-integer-into-a-sorted-list%23new-answer', 'question_page');

);

Post as a guest













































































Popular posts from this blog

How to check contact read email or not when send email to Individual?

Displaying single band from multi-band raster using QGIS

How many registers does an x86_64 CPU actually have?