# JavaScript ES6 one-liners: merge two sorted lists

### Sergei ・1 min read

One of the steps in the merge-sort algorithm is merging two sorted lists together. In the spirit of doing everything on a single line (see my other posts), here is an admittedly hokey one-liner for merging two lists together (it creates a new merged list and clobbers the second of the two original sorted lists):

```
const orderedList1 = [1,3,5,7,9];
const orderedList2 = [0,2,5,8,11];
console.log([...orderedList1.reduce((a, e) =>
[...orderedList2.some(r =>
e > r? a.push(orderedList2.shift()): false)?a:a, e], []),
...orderedList2]);
// [ 0, 1, 2, 3, 5, 5, 7, 8, 9, 11 ]
```

A bit of an explanation for this monstrosity:

The outer "reduce" starts with an empty list, goes through each element of the first list, extracts all the elements of the second list that are ahead of the current element of the first list and inserts them into the merged list, and then inserts the current element. Finally, the remainder of the second list, if any, is appended at the end of the merged list. The fake ternary operator smuggles in the "some" call inside the spread operator collecting the merged list in progress. Not sure if this can be done more neatly.

That's also slower than the original.

shiftcost O(m)somecosts O(m) andreduceCosts O(n) where m is the length of orderedList2 and n the length of orderedList1 so I can cost as much as O(n*m*m)A very good point about the complexity of

shift! I missed that one.someis not as bad, since it quits on firsttrue, and the next loop it continues where it left off, so orderedList2 is scanned at most once in total, not each time. I could not figure out a simple way to maintain the starting index in orderedList2 during the merge, to avoid actually removing elements from it, while keeping the code to a single statement.Seems easy to forget that the elegant new collection operators are still O loops under the hood.

Yep, I tried to remember it, yet had made a basic mistake of assuming that Array.prototype.shift() is O(1), yet it is O(n) in its most common implementations, including the one specified in the ECMAScript 2015 spec. The code would be O(n1+n2) if it used orderedList2[index_of_first_not_yet_merged_element] instead of

shift.As much as we have to consider big-o, I'm surprised someone hasn't rebuilt pgsql as a wasm 😂

Just... Whatever, batch insert and order by lol

Hah. An inverse of this?

I actually ported a legacy C code to wasm/emscripten, but source debugging sucks with wasm, so dropped that effort.

Why not ?

Because list merging is a step in merge-sort, so this becomes a chicken-and-egg problem if you write your own merge-sort. Certainly if you are allowed to used

sort, there is no reason to explicitly merge lists element-by-element. Also,sortis O(n log(n)) and merging is O(n) where n is the combined length of the lists. Well, it is supposed to be O(n) when properly implemented, theshiftfunction I used is a poor choice, since its complexity is O(n) not O(1), as pointed out by Theofanis in the other reply.