Implementing merge sort in C++ using multithreading

We get an unsorted array of integers. The task is to sort the array using merge sort technique implemented through multi-threading

MERGE SORTS

Merge sort is a sorting technique based on divide and conquer technique where we will divide the array into two equal halves , and then combine them in a sorted manner.

The algorithm to implement merge sort is

• Check if there is an element

• Otherwise, split the data in half recursively , until it can no longer be divided.

• Finally, merge the smaller lists into a new list in sorted order.

Multi-threading

In the operating system, Threads are lightweight processes responsible for performing some tasks. Threads share common resources to perform tasks concurrently.

Multi-threading is an implementation of multitasking. We can run multiple threads on a single processor to execute tasks concurrently. It breaks down specific operations within a single application into separate threads. Each thread can run in parallel.

For example:

In −int arr[] = {3, 2, 1, 10, 8, 5, 7, 9, 4}

Output−The sorted array is: 1, 2, 3, 4, 5, 7, 8, 9, 10

Explanation-We get a Unsorted array with integer values. Now we will sort the array using multi-threaded merge sort.

In −int arr[] = {5, 3, 1, 45, 32, 21, 50} p>

Output−After sorting The array of is: 1, 3, 5, 21, 32, 45, 50

Explanation−We are given an unsorted array with integer values. Now we will sort the array using multi-threaded merge sort.

The methods used in the program below are as follows -

• We will start generating random numbers by using rand() method in C STL.

• Create an array of type pthread_t, that is, P_TH[thread_size].

Start a FOR loop from i to 0 until i is less than the size of the thread. Inside the loop, the pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL) method is called to create a thread with the given array value.

• Call the function as combine_array(0, (size/2 - 1)/2, size/2 - 1), combine_array(size/2, size/2 (size - 1-size/2)/2, size-1) and merge_array(0, (size-1)/2, size-1)

• print the integer type arr[] sorted array in .

Internal function void* Sorting_Threading(void* arg)

• Declare a variable from set_val to temp_val, first set_val * (size / 4 ), end is (set_val 1) * (size / 4) - 1, mid_val is first (end - first) / 2

• Check IF first is less than end then call Sorting_Threading(first, mid_val), Sorting_Threading(mid_val 1, end) and combine_array(first, mid_val, end);

• ##inside function void Sorting_Threading(int first, int end)
  • Declare the variable as mid_val to first (end - first) / 2

  • Check if IF is less than end first, then call Sorting_Threading(first, mid_val ), Sorting_Threading(mid_val 1, end) and merge_array(first, mid_val, end)

• Internal function void merge_array(int first, int mid_val, int end)
  • Declare variables as int* start to new int[mid_val - first 1], int* last to new int[end - mid_val], temp_1 to mid_val - first 1, temp_2 to end - mid_val, i, j, k to first.
    li>
  • Start a FOR loop from i to 0 until i is less than temp_1. Inside the loop, set start[i] to arr[i first].

  • Start a FOR loop from i to 0 until i is less than temp_2. Inside the loop, set last[i] to arr[i mid_val 1]

  • set i to j to 0. Start looping when i is less than temp_1 and j is less than temp_2. During this time, check if IF start[i] is less than last[j], then set arr[k] to start[i]. Otherwise, set arr[k ] = last[j ]

  • Start when i is less than temp_1, then set arr[k ] = start[i ]. Start when j is less than temp_2, then set arr[k ] to last[j ]

##Example

#include <iostream>
#include <pthread.h>
#include <time.h>
#define size 20
#define thread_size 4
using namespace std;
int arr[size];
int temp_val = 0;
void combine_array(int first, int mid_val, int end){
   int* start = new int[mid_val - first + 1];
   int* last = new int[end - mid_val];
   int temp_1 = mid_val - first + 1;
   int temp_2 = end - mid_val;
   int i, j;
   int k = first;
   for(i = 0; i < temp_1; i++){
      start[i] = arr[i + first];
   }
   for (i = 0; i < temp_2; i++){
      last[i] = arr[i + mid_val + 1];
   }
   i = j = 0;
   while(i < temp_1 && j < temp_2){
      if(start[i] <= last[j]){
         arr[k++] = start[i++];
      }
      else{
         arr[k++] = last[j++];
      }
   }
   while (i < temp_1){
      arr[k++] = start[i++];
   }
   while (j < temp_2){
      arr[k++] = last[j++];
   }
}
void Sorting_Threading(int first, int end){
   int mid_val = first + (end - first) / 2;
   if(first < end){
      Sorting_Threading(first, mid_val);
      Sorting_Threading(mid_val + 1, end);
      combine_array(first, mid_val, end);
   }
}
void* Sorting_Threading(void* arg){
   int set_val = temp_val++;
   int first = set_val * (size / 4);
   int end = (set_val + 1) * (size / 4) - 1;
   int mid_val = first + (end - first) / 2;
   if (first < end){
      Sorting_Threading(first, mid_val);
      Sorting_Threading(mid_val + 1, end);
      combine_array(first, mid_val, end);
   }
}
int main(){
   for(int i = 0; i < size; i++){
      arr[i] = rand() % 100;
   }
   pthread_t P_TH[thread_size];
   for(int i = 0; i < thread_size; i++){
      pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL);
   }
   for(int i = 0; i < 4; i++){
      pthread_join(P_TH[i], NULL);
   }
   combine_array(0, (size / 2 - 1) / 2, size / 2 - 1);
   combine_array(size / 2, size/2 + (size-1-size/2)/2, size - 1);
   combine_array(0, (size - 1)/2, size - 1);
   cout<<"Merge Sort using Multi-threading: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   return 0;
}

Output

If we run the above code it will generate the following output

Merge Sort using Multi-threading: 15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93

The above is the detailed content of Implementing merge sort in C++ using multithreading. For more information, please follow other related articles on the PHP Chinese website!