cancel
Showing results for 
Search instead for 
Did you mean: 
Reply
Ariser
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.

 

  • Elements have a sort key and additional payload
  • 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 keydata
2this
5conundrum
5or
8or 
11my 

 

Array two:

sort keydata
1Solve
5riddle
10hold 
14beer

 

Desired output:

sort keydata

1

Solve
2this
5conundrum
5or
5riddle
8or
10hold
11my
14beer

 

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
Paulie78
Super User III
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.

 

View solution in original post

6 REPLIES 6
Paulie78
Super User III
Super User III

You can do it like this:

https://ibb.co/v19TWY9

MergeArrays.png

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?

 

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.

Ariser
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. 

Paulie78
Super User III
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.

 

View solution in original post

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. 

Paulie78
Super User III
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.

Helpful resources

Announcements
MPA User Group

Welcome to the User Group Public Preview

Check out new user group experience and if you are a leader please create your group

MBAS on Demand

Microsoft Business Applications Summit sessions

On-demand access to all the great content presented by the product teams and community members! #MSBizAppsSummit #CommunityRocks

MBAS Attendee Badge

Claim Your Badge & Digital Swag!

Check out how to claim yours today!

secondImage

Are Your Ready?

Test your skills now with the Cloud Skill Challenge.

Top Solution Authors
Users online (46,409)