Merge k sorted arrays
Merge k sorted arrays using Min heap
Algorithm:
- Create a HeapNode class with following properties
- key
- arrayId
- arrayIndex
- Create array to hold merge result
- Add first element from all sorted array to MinHeap
- Iterate 0 to n*k
- remove min from MinHeap and add to output_array
- If remove _element’s array has more element then
- add add element from that array to MinHeap
- Else
- Add some dummy high number to MinHeap
- Return output_array
Source Code:
Github: MergeKSort.java
Output:
1 3 8 9 15 20 48 58 67 68 2 10 22 49 60 After KSort: 1 2 3 8 9 10 15 20 22 48 49 58 60 67 68