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.
Top comments (8)
That's also slower than the original. shift cost O(m) some costs O(m) and reduce Costs 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)
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.
A very good point about the complexity of shift! I missed that one. some is not as bad, since it quits on first true, 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.
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, sort is 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, the shift function I used is a poor choice, since its complexity is O(n) not O(1), as pointed out by Theofanis in the other reply.