CODEWITHSUNDEEP
c++arrayspthreadsmergesort
Carlos Arronte Bello
Carlos Arronte Bello

Reputation: 429

Merge sort wih pthreads not working in c++

I have this code. 

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <iostream>
using namespace std;


int N;
int* a ;
/* structure for array index
 * used to keep low/high end of sub arrays
 */
typedef struct Arr
{
    int low;
    int high;
} ArrayIndex;

void merge(int low, int high)
{
    int mid = (low+high)/2;
    int left = low;
    int right = mid+1;

    int b[high-low+1];
    int i, cur = 0;

    while(left <= mid && right <= high)
    {
        if (a[left] > a[right])
            b[cur++] = a[right++];
        else
            b[cur++] = a[right++];
    }

    while(left <= mid) b[cur++] = a[left++];
    while(right <= high) b[cur++] = a[left++];
    for (i = 0; i < (high-low+1) ; i++) a[low+i] = b[i];
}

void * mergesort(void *a)
{

    ArrayIndex *pa = (ArrayIndex *)a;
    int mid = (pa->low + pa->high)/2;

    ArrayIndex aIndex[N];
    pthread_t thread[N];

    aIndex[0].low = pa->low;
    aIndex[0].high = mid;

    aIndex[1].low = mid+1;
    aIndex[1].high = pa->high;

    if (pa->low >= pa->high) return 0;

    int i;
    for(i = 0; i < N; i++) pthread_create(&thread[i], NULL, mergesort, &aIndex[i]);
    for(i = 0; i < N; i++) pthread_join(thread[i], NULL);

    merge(pa->low, pa->high);

    //pthread_exit(NULL);
    return 0;
}

int main()
{
    int s;
    cout << "\nPlease enter a number of threads:" << endl;
    cout << "-> ";
    cin >> N;
    do
    {
        cout << "\nPlease enter the array size:" << endl;
        cout << "-> ";
        cin >> s;
        if(s%N != 0)
        {
            cout << "\n Number not divisible by: "<< N << endl;
        }
    }
    while (s%N != 0);
    a = new int[s];  // Allocate n ints and save ptr in a.
    for (int i=0; i<s; i++)
    {
        a[i] = rand() % 100 + 1;;    // Initialize all elements to zero.
       // printf ("%d ", a[i]);
    }
    ArrayIndex ai;
    ai.low = 0;
    ai.high = sizeof(a)/sizeof(a[0])-1;
    pthread_t thread;

    pthread_create(&thread, NULL, mergesort, &ai);
    pthread_join(thread, NULL);

    int i;
    for (i = 0; i < s; i++) printf ("%d ", a[i]);
    cout << endl;

    return 0;
}

So basically the code ask to the user the numbers of threads, then the size of the array and have to sort the array. The issue is that the mergesort it´s not working, when I print the array is not ordered.

Upvotes: 1

Views: 364

Answers (1)

sp2danny
sp2danny

Reputation: 7644

I have found one bug:

while(left <= mid && right <= high)
{
    if (a[left] > a[right])
        b[cur++] = a[right++];
    else
        b[cur++] = a[right++];
}

As you can see, the if and the else part execute the exact same thing.
There might be other bugs, a tip is to first convert the algorithm to not use threads,
and step through the algorithm in a debugger.

Upvotes: 1

Related Questions