Speed comparison of parallel merge sort and qsort

Parallel merge sort is my course assignment. And I feel interested that which speed is fast between parallel merge sort and qsort. Therefore, here is an experiment about speed test in parallel merge sort and qsort.

system: linux

Here is parallel merge sort:

	/****** Create by Hui-Jou Chou on 2/19/2016,
	parallel computing assignment_1 ******/
	#include <stdio.h>
	#include <stdlib.h>
	#include <mpi.h>
	#include <time.h>
	double startT, stopT;
	/****** Merge Function ******/
	int* merge(int* arr, int low, int* b, int high)
	{
	int* new_arr = (int*)malloc(sizeof(int)*(high+low));
	int i=0, j=0, k=0;
	while(i<low && j<high)
	{
	if(arr[i]<=b[j]) new_arr[k++]=arr[i++];
	else new_arr[k++]=b[j++];
	}
	while (i < low) new_arr[k++]=arr[i++];
	while (j < high) new_arr[k++]=b[j++];
	for(i=0; i<low;i++)
	{
	arr[i]=new_arr[i];
	}
	for(i=0;i<high;i++)
	{
	b[i]=new_arr[low+i];
	}
	return new_arr;
	}
	/****** Recursive Merge Function ******/
	void Mergesort(int* arr, int low, int high)
	{
	int* c;
	if(low<high)
	{
	int mid=(high+low)/2;
	int lowercount=mid-low+1;
	int highercount=high-mid;
	Mergesort(arr,low, mid);
	Mergesort(arr,mid+1,high);
	c = merge(arr+low,lowercount,arr+mid+1,highercount);
	}
	}
	int main(int argc, char *argv[]){
	/****** Open file ******/
	FILE *fp=fopen(argv[1],"r");
	if(fp == NULL)
	{
	perror("Error in opening file");
	return(-1);
	}
	/****** Create array and parameters ******/
	int* num=(int*)malloc(sizeof(int)*(1000));
	int chunk_size;
	int numOfElements=0;
	/****** Initialize MPI ******/
	int size, rank;
	MPI_Init(&argc,&argv);
	MPI_Comm_rank( MPI_COMM_WORLD, &rank);
	MPI_Comm_size( MPI_COMM_WORLD, &size);
	startT=clock();
	/****** Input unsorted array ******/
	if(rank==0)
	{
	while(!feof(fp))
	{
	fscanf(fp,"%d ",num+numOfElements);
	numOfElements++;
	}
	}
	/****** Broadcast numOfElements ******/
	MPI_Bcast(&numOfElements, 1, MPI_INT,0, MPI_COMM_WORLD);
	printf("Hello from process %d of %d \n",rank,size);
	/****** Divide the array into equal-sized chunks ******/
	chunk_size = numOfElements/size+1;
	/****** Create a buffer that will hold a subset of the array ******/
	int *sub_array = malloc(sizeof(int) * chunk_size);
	/****** Scatter the array to all processes ******/
	MPI_Scatter(num, chunk_size, MPI_INT, sub_array, chunk_size, MPI_INT, 0, MPI_COMM_WORLD);
	/****** Perform each mergesort on each process ******/
	Mergesort(sub_array, 0, chunk_size-1);
	/****** log_2P parallel merge steps ******/
	int s=chunk_size;
	int step;
	int other_size;
	for(step=1; step<size; step=2*step)
	{
	if(rank%(2*step))
	{
	MPI_Send(&s,1,MPI_INT,rank-step ,0,MPI_COMM_WORLD);
	MPI_Send(sub_array, s, MPI_INT,rank-step ,0,MPI_COMM_WORLD);
	break;
	}
	else
	{
	if(rank+step<size)
	{
	MPI_Recv(&other_size, 1,MPI_INT,rank+step,0,MPI_COMM_WORLD,MPI_STATUS_IGNORE);
	int* other=(int*)malloc(sizeof(int)*other_size);
	MPI_Recv(other, other_size, MPI_INT, rank+step, 0, MPI_COMM_WORLD,MPI_STATUS_IGNORE);
	sub_array=merge(sub_array,s,other,other_size);
	s=s+other_size;
	free(other);
	}
	}
	}
	stopT=clock();
	/****** output file ******/
	if(rank==0)
	{
	int iter;
	int count=0;
	printf("%d processors, %f secs\n", size, (stopT-startT)/CLOCKS_PER_SEC);
	FILE *output=fopen(argv[2],"w");
	for (iter =0; iter<s; iter++)
	{
	if(sub_array[iter]==0 && count<s-numOfElements)
	{
	count++;
	continue;
	}
	fprintf(output, "%d ",sub_array[iter]);
	}
	fclose(output);
	}
	/****** Clean up rest ******/
	free(sub_array);
	free(num);
	/****** Finalize MPI ******/
	MPI_Finalize();
	return 0;
	}

view raw parallel_mergesort.c hosted with ❤ by GitHub

output:8 processors 0.000548s
           8 processors 0.000482s
           8 processors 0.000421s
           8 processors 0.000473s
           8 processors 0.000402s

 Here is qsort:

	#include <stdio.h>
	#include <stdlib.h>
	#include <time.h>
	double startT,stopT;
	int cmpfunc( const void *a, const void *b)
	{
	return (*(int*)a - *(int*)b);
	}
	int main(int argc, char* argv[])
	{
	FILE *fp=fopen(argv[1],"r");
	if(fp ==NULL){
	perror("Error in opening file");
	return(-1);
	}
	int* input= malloc(sizeof(int)*1000);
	startT=clock();
	int iter=0;
	while(!feof(fp)){
	fscanf(fp, "%d",input+iter);
	iter++;
	}
	qsort(input, iter,sizeof(int),cmpfunc);
	stopT=clock();
	printf("%f secs\n", (stopT-startT)/CLOCKS_PER_SEC);
	FILE *output=fopen(argv[2],"w");
	for(int i=0; i<iter; i++){
	fprintf(output,"%d ",input[i]);
	}
	fclose(output);
	free(input);
	return 0;
	}

view raw q_sort.c hosted with ❤ by GitHub

output:  0.000691 secs
             0.000635 secs
             0.000551 secs
             0.000505 secs
             0.000708 secs

Discussion:

   There is no significant difference between parallel merge sort and qsort. I will post the plot analysis later.