cancel
Showing results for
Did you mean:
Regular Visitor

## How to merge presorted arrays of same type? Zipper algorithm needed!

I have two arrays of the same structure, i.e. the elements have the same properties.

• Both arrays are already sorted by the key (pulled from sharepoint with ODATA sorting)
• In an array there can be more than one element with the same sort key
• elements with the same sort key can appear in both arrays

The outcome should be a sorted array with all elements. I.e. the number of elements should be exactly the sum of the ones from the source arrays. If there are groups of more than one element with the same key, sort order within that groups is irrelevant.

I also don't care if the original arrays are emptied or modified to cut edges. Only the output is of interest.

Currently I do that merging by splitting of array B with two filtering operations for every element of array A. After that I union(lower part, new element, upper part) the stuff together. But this is inefficient and doesn't scale well.

I'll try to illustrate, what I want to achieve:

Array one:

 sort key data 2 this 5 conundrum 5 or 8 or 11 my

Array two:

 sort key data 1 Solve 5 riddle 10 hold 14 beer

Desired output:

 sort key data 1 Solve 2 this 5 conundrum 5 or 5 riddle 8 or 10 hold 11 my 14 beer

As said, the order of the elements with same sort key (5 in this case) is irrelevant, so "Solve this or conundrum ridlle or hold my beer" is also a valid outcome. However everything else should be sorted according the key.

1 ACCEPTED SOLUTION

Accepted Solutions
Super User III

I did it like this:

https://ibb.co/3hcTnbh

Quite an interesting problem to solve. Output is:

``````[
{
"sortKey": "1",
"data": "Solve"
},
{
"sortKey": "2",
"data": "this"
},
{
"sortKey": "5",
"data": "conundrum"
},
{
"sortKey": "5",
"data": "or"
},
{
"sortKey": "5",
"data": "riddle"
},
{
"sortKey": "8",
"data": "or"
},
{
"sortKey": "10",
"data": "hold"
},
{
"sortKey": "11",
"data": "my"
},
{
"sortKey": "14",
"data": "beer"
}
]``````

Explanation:

First the lowest and highest sort keys of both arrays are found.

Then a range is created based on the values of the low and high sort key.

An apply to each loop is started based on the array created by the range, which would look like this:

``[ 1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  11,  12,  13,  14 ]``

Within the loop both arrays are filtered where sortKey matches the current iteration from the range.

If there are matches to the sort key, then an apply to each loop runs for each of the results in the filter array. Any results get appended to the array variable defined at the top of the flow. If there are no results in the filter array, then it simply moves on.

At the end you have the merged output.

6 REPLIES 6
Super User III

You can do it like this:

https://ibb.co/v19TWY9

The expression in merged is:

``addProperty(item(), 'surname', outputs('Array_Two')[variables('index')]['surname'])``

The final compose (outside of the loop) contains the merged array. Does it make sense?

Regular Visitor

Thanks for your reply, but that is not what I'm searching for. The arrays you used in your example are of different type. The one has elements with the keys: gender and name, and the other has only surname. Your proposed algorithm works only if the second array has at least as many elements as the first one. And the output of your example with two elements in each array has two elements as well. I need 4 elements in the output. I think I'll add more information to my question to better illustrate my goal.

Regular Visitor

Are there no ideas for this simple problem?

Currently I write all data into an external list and reread it using the external sort algorithms. However I'm dissatified with the possibilities concerning sorting.

Super User III

I did it like this:

https://ibb.co/3hcTnbh

Quite an interesting problem to solve. Output is:

``````[
{
"sortKey": "1",
"data": "Solve"
},
{
"sortKey": "2",
"data": "this"
},
{
"sortKey": "5",
"data": "conundrum"
},
{
"sortKey": "5",
"data": "or"
},
{
"sortKey": "5",
"data": "riddle"
},
{
"sortKey": "8",
"data": "or"
},
{
"sortKey": "10",
"data": "hold"
},
{
"sortKey": "11",
"data": "my"
},
{
"sortKey": "14",
"data": "beer"
}
]``````

Explanation:

First the lowest and highest sort keys of both arrays are found.

Then a range is created based on the values of the low and high sort key.

An apply to each loop is started based on the array created by the range, which would look like this:

``[ 1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  11,  12,  13,  14 ]``

Within the loop both arrays are filtered where sortKey matches the current iteration from the range.

If there are matches to the sort key, then an apply to each loop runs for each of the results in the filter array. Any results get appended to the array variable defined at the top of the flow. If there are no results in the filter array, then it simply moves on.

At the end you have the merged output.

Regular Visitor

That's a really interesting solution. You evaded iterating over both arrays numerous times by externalising the progression with that range statement. Depending on the API actions consumed by the filter operations it may even beat my interim solution with an external list.

It will probably scale acceptably with growing array size.

I think it can also be extended to non-integer sort keys.

Super User III

It was the first time I had a legit reason to use the range function, it was a fun problem to solve. I think if I was trying to solve this for real, I'd probably use an Azure function.

Announcements

Check out how to claim yours today!

#### Welcome to the User Group Public Preview

Test your skills now with the Cloud Skill Challenge.

Top Solution Authors
Top Kudoed Authors
Users online (51,600)