So I have 5 blocks (let's say of size 2000 items) each of sorted data. Is there an algorithm that would be able to take advantage of this attribute to optimize sorting the whole 10,000 items?
2
-
Kinda messed up the name. I am simply sorting several sorted arrays together into one big sorted array in the fastest way possibleRChuDChu– RChuDChu2018-11-06 22:26:20 +00:00Commented Nov 6, 2018 at 22:26
-
2geeksforgeeks.org/merge-k-sorted-arraysKaidul– Kaidul2018-11-06 22:42:30 +00:00Commented Nov 6, 2018 at 22:42
Add a comment
|
1 Answer
Don't know any but you can make list of the smallest for each block, that is 5 elements, remember which block they came from.
Then sort them.
Remove the smallest and add to the result
Take the next smallest from the list that the smallest was from and place it in the correst sorted position.
3 Comments
Jim Mischel
That's a horribly expensive way to do it. Use a priority queue (usually a binary heap) instead of sorting.
Surt
@JimMischel that was what i tried to say, sorting the smallest element of each is making a prioriy queue.
Jim Mischel
There is a big difference between using a heap-based priority queue and sorting an array of items. The merge with a priority queue is O(n log k), where n is the total number of items, and k is the number of lists. Your method that uses sorting to select the next highest is O(n * (k log k)).