Sort numbers stored on different machines

Introduction:

In this problem, we are given a number of machines. Each machine has some numbers which are in sorted order. But there is no fixed number of numbers in each machine. The output of the number from each machine is in sorted decreasing order.

Let us see this by taking an example.

Approach-1:

Example:

Machine M1 contains 3 numbers: {30, 40, 50}

Machine M2 contains 2 numbers: {35, 45}

Machine M3 contains 5 numbers: {10, 60, 70, 80, 100}

Output: {10, 30, 35, 40, 45, 50, 60, 70, 80, 100}

We can represent each stream of numbers in the form of a linked list. With the help of a min heap, we can print all the numbers in a sorted order. With the help of the below steps, we can perform the operation.

• First, we have to store the head pointers of the linked lists in a minute. The size of the mini heap is N. Here, N represents the number of machines.
• Then, we have to extract the minimum heap available in the mini heap. Then we have to Update the minHeap by replacing the head of the minHeap with the next number from the linked list or by replacing the head of the minHeap with the last number in the minHeap followed by decreasing the size of the heap by 1.

Let's solve the above problem with the help of programming language.

Implementation in C++:

Output:

Explanation:

In the above code, we have implemented the above problem approach in C++ language. Here, first, we have created a linked list and then added some elements to that linked list. After that, we implemented some methods, and with the help of those methods, we were able to solve the above problem.

Approach 2:

In this approach, we are going to merge the different sorted lists in different machines. Here, we have to create a mergeList(), which accepts the vector of the linked list; then, it merges them into a single sorted linked list with the help of a mean heap. Then we have to create another externalSort() which convert the linked list into vector. Then, we have to call the mergeList() to sort the list. Then, we have to print the list.

Let us see this approach in the programming language.

Implementation in C++:

Code:

Output:

Explanation:

In the above code, we have created some functions in C++ to manipulate the arrays, as per what we discussed in the above approach. After successfully sorting the array, we printed it.