Generic merge-sort algorithm

SystemVerilog
,
1

Hi,

I have an array that I would like to sort, but keep the indices attached.
For that matter I created a struct:

typedef struct {
    int val;
    int id;
} val_id;

The issue is that I need to imitate the design sorting method which is merge sort algorithm, and I can’t just use the built-in sort function

e.g. for the values '{121, 94, 89, 94} I have the following array:
val_id vals[4] = '{'{121,0},'{94,1},'{89,2},'{94,3}};

using merge-sort will result [val(id)]
89(2), 94(3), 94(1), 121(0)
while using vals.sort with (item.val); will result
89(2), 94(1), 94(3), 121(0)

The reason I need this, is for using the ids for further computations

Before I implement merge-sort for that -

  1. Is there any way to implement merge-sort using the built-in sort function?
  2. If I do implement this function, I would like to make it generic, like built-in sort function can have any data type, as long it comes with a “with” clause
  3. Is there another way to keep the indices after sorting?

Thanks

2

Do you have the results backwards? A merge-sort is supposed to leave equal items in the same order. 94(1), 94(3) is the original order.

You can use

vals.sort with ({item.val,item.id});
3

You are correct, but due to design issues the merge was implemented it a bit differently -

In my case, there are always 4 inputs, and there are 5 comparison to get the total sort:

  1. sort between arr[0] and arr[1]
  2. sort between arr[2] and arr[3]
  3. sort between arr[0] and arr[2] (comparison between minimums)
  4. sort between arr[1] and arr[3] (comparison between maximums)
  5. sort between arr[1] and arr[2] (comparison between middles)

so in my example if we start with 121(0) 94(1) 89(2) 94(3) the algorithm will be:

  1. 94(1) 121(0) 89(2) 94(3)
  2. 94(1) 121(0) 89(2) 94(3)
  3. 89(2) 121(0) 94(1) 94(3)
  4. 89(2) 94(3) 94(1) 121(0)
  5. 89(2) 94(3) 94(1) 121(0)

I see how it different from the proper merge-sort algorithm, and I guess there is no guarantee to the order between equal items.

I tried to avoid copying the design implementation, and find a more generic way to imitate the design (if the design will change to sort more items), but now I can’t see a way to do so