#include <stdio.h>
#include <omp.h>
#include <math.h>
#include <stdlib.h>
void quickSort (int a[], int lo, int hi);
int main()
{
int N = 10000000 ;
int i , j , id ;
int *array = (int*)malloc(sizeof(int)*N);
int *temp = (int*)malloc(sizeof(int)*N);
for(i=0;i<N;i++)
{
temp[i]=rand()%100+1;
}
#pragma omp parallel num_threads(4)
{
id= omp_get_thread_num();
if(id==0)
{
quickSort(temp,0,N/4-1);
}
if(id==1)
{
quickSort(temp,N/4,N/2-1);
}
if(id==2)
{
quickSort(temp,N/2,(3*N/4)-1);
}
if(id==3)
{
quickSort(temp,(3*N/4)-1,N-1);
}
}
#pragma omp parallel
{
id= omp_get_thread_num();
if(id==0)
{
int i1=0;
int j1=N/4;
for(int k=0;k<N/2;k++)
{
if(temp[i1]<temp[j1])
{
array[k]=temp[i1];
i1++;
if(i1>N/4)
{
for(i1=j1;i1<N/2;i1++)
{
array[k]=temp[i1];
k++;
}
}
}
else if(temp[j1]<=temp[i1])
{
array[k]=temp[j1];
j1++;
if(j1>N/2)
{
for(j1=i1;j1<N/4;j1++)
{
array[k]=temp[j1];
k++;
}
}
}
}
}
if(id==2)
{
int i2=N/2;
int j2=(3*N/4);
for(int l=N/2;l<N;l++)
{
if(temp[i2]<temp[j2])
{
array[l]=temp[i2];
i2++;
if(i2>(3*N/4))
{
for(i2=j2;i2<N;i2++)
{
array[l]=temp[i2];
l++;
}
}
}
else if(temp[j2]<=temp[i2])
{
array[l]=temp[j2];
j2++;
if(j2>N)
{
for(j2=i2;j2<3*N/4;j2++)
{
array[l]=temp[j2];
l++;
}
}
}
}
}
}
i=0;
j=N/2;
for(int k=0;k<N;k++)
{
if(array[i]<array[j])
{
temp[k]=array[i];
i++;
if(i>(N/2))
{
for(i=j;i<N;i++)
{
temp[k]=array[i];
k++;
}
}
}
else if(array[j]<=array[i])
{
temp[k]=array[j];
j++;
if(j>N)
{
for(j=i;j<N/2;j++)
{
temp[k]=array[j];
k++;
}
}
}
}
for(i=0;i<N;i++)
printf("result %d = %d \n",i,temp[i]);
}
void quickSort (int a[], int lo, int hi)
{
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];
// partition
do
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
// recursion
if (lo<j) quickSort(a, lo, j);
if (i<hi) quickSort(a, i, hi);
}
