Merge of Two Sorted Memories -> how to merge in HW?

[ivlsi]

Hi All,

There are two memories with sorted data (two sorted arrays).

What's the best HW implementation to merge this two sorted memory (data in the meories) into a single sorted array (sorted data over these two memories).

Thank you!

 

[ads-ee]

An FSM that does a sort algorithm?

1. read both memories at first entry
2. compare values
3. write sorted value into 3rd memory (size of both arrays)
4. read memory that you wrote value into 3rd memory
5. repeat starting at 2 until you've read all locations of both memories
6. finally write the last sorted value into 3rd memory.

 

[ivlsi]

It should be implemented without additional memory

 

[ads-ee]

It should be implemented without additional memory

Now I see, of course it does...that's because it must be a homework assignment.

Doing it without an extra memory (i.e. in-place) is relatively easy to do, but you will need to have a holding register for the currently indexed values as opposed to accessing them from the memory directly. Now go off and think about your homework and "learn by doing" instead of "being told what to do".

If you never learn to do things yourself you'll never become successful as an engineer.

 

[ivlsi]

ads-ee, what's the matter?

It should be done using a Swap Algorithm. Do you know to do it in another way or just teach others what to do?

 

[ads-ee]

ads-ee, what's the matter?

How about for starters you didn't mention half of what you've added from the first post. Seems to be a reoccurring theme with your posting style. :thumbsdown:

It should be done using a Swap Algorithm. Do you know to do it in another way

Yeah I alluded to that in my previous post. That is probably the most logic efficient methods, but you could improve the performance by using dual port memories and sort 2 words at a time (doing 4 reads) and doubling the amount of logic and performance.

Sorting isn't something that lends itself to parallelism, without a huge trade off in implementation size.