# Inserting an integer into a list while maintaining descending order

Define a function g with two arguments, w and n, where w a list of integers sorted in descending order ands n is an integer.; g should return a list produced by inserting n into w in a way that maintains descending order.

For example g[{9, 8, 5, 3, 2, 1}, 6] must return {9, 8, 6, 5, 3, 2, 1}.

How cam I do this in the best way in functional programming?

• g[l_List, n_Integer] := Sort[Flatten[{l, n}], Greater] – corey979 Nov 26 '16 at 21:48
• Hello, the code is doing Map functions and i´m not able to use Sort. – Paulo Rodrigues Nov 26 '16 at 21:52
• This is not the answer – Paulo Rodrigues Nov 26 '16 at 22:08
• The answer of corey979 does just what you asked... how is it "not the answer"? – bill s Nov 26 '16 at 22:23
• But i cant do the Sort* – Paulo Rodrigues Nov 26 '16 at 22:30

If Sort is not allowed then

Clear[g]

g[{i : _Integer ..}, n_Integer] :=
{Cases[{i}, _?(# > n &)], n,
Cases[{i}, _?(# < n &)]} // Flatten

g[{9, 8, 5, 3, 2, 1}, 6]

{9, 8, 6, 5, 3, 2, 1}


Or

Clear[g]

g[{i : _Integer ..}, n_Integer] :=

Insert[SplitBy[{i}, # > n &], n, 2] // Flatten

g[{9, 8, 5, 3, 2, 1}, 6]

{9, 8, 6, 5, 3, 2, 1}


Or

Clear[g]

g[{i : _Integer ..},
n_Integer] :=
{i} /. {s___, u_?(# > n &), l_?(# < n &), e___} :>
{s, u, n, l, e}

g[{9, 8, 5, 3, 2, 1}, 6]

{9, 8, 6, 5, 3, 2, 1}


Here are three more ways to do it.

g[d_List, n_Integer] :=
Flatten[Insert[SplitBy[d, n >= # &], {n}, 2]]

g[d_List, n_Integer] :=
Flatten[Insert[GatherBy[d, n >= # &], {n}, 2]]


This next is just using Reap and Sow to do the gathering.

g[d_List, n_Integer] :=
Flatten[Insert[Reap[If[# > n, Sow[#, 1], Sow[#, 2]] & /@ d][], {n}, 2]]


For all of these

g[{9, 8, 5, 3, 2, 1}, 6]


gives

{9, 8, 6, 5, 3, 2, 1}

• Are all of these working in $\log(N)$? – mavzolej Nov 2 '18 at 21:37