\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Improving of Quicksort Algorithm Performance by Sequential Thread or Parallel Algorithms},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2012-01-15 (revised: 15 January 2012)}
\def\TheID{\makeatother }
\def\TheDate{2012-01-15}
\title{Improving of Quicksort Algorithm Performance by Sequential Thread or Parallel Algorithms}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Abdulrahman Helal  Alruwaili}

             \affil[1]{  King Saud University, Master of Computer Science Program}

\renewcommand\Authands{ and }

\date{\small \em Received: 16 December 2011 Accepted: 4 January 2012 Published: 15 January 2012}

\maketitle


\begin{abstract}
        


Quicksort is well-know algorithm used for sorting, making O(n log n) comparisons to sort a dataset of n items. Being a divide-and-conquer algorithm, it is easily modified to use parallel computing. The aim of this paper is to evaluate the performance of parallel quicksort algorithm and compare it with theoretical performance analysis. To achieve this we implement a tool to do both sequential and parallel quicksort on randomly generated arrays of different size in several runs to provide us with enough data to draw conclusions about the efficiency of using the capability of modern multicore processors together with algorithms designed to increase the speed of sorting large arrays.

\end{abstract}


\keywords{Parallel computing, Parallel algorithms, Parallel Computing, Quicksort.}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{Introduction and motivation}]{Introduction and motivation}\par
orting is among the fundamental problems of computer science. Sorting of different datasets is present in most applications, ranging from simple user applications to complex software. Today, in this modern age, the amount of data to be sorted is often so big, that even the most efficient sequential sorting algorithms become the bottleneck of the application. It may be a database or scientific data.\par
Today, it is said that the problem is not the lack of data but the need to sort and search in the huge amount of data available to us. To be able to do those tasks efficiently with the data available, the speed of sorting becomes critical. A lot of work was done to improve the speed of traditional sequential sorting algorithms, be it optimizing the pivot selection for quicksort or trying to come up with new, adapting sorting algorithms.\par
With the appearance of parallel computing, new possibilities have appeared to remove this bottleneck and improve the performance of known sorting algorithms by modifying them for parallel execution. At first, this was achieved using distributed computing, however with the hardware available today, it is possible to do this even on home computers thanks to their multicore processors.\par
In this paper, we present a parallel version of the well know quicksort algorithm and compare its performance to the performance of its simpler, sequential quicksort algorithm. Comparing their performance, we look for the threshold T, the size of the array, at which the parallel algorithm becomes actually slower than the sequential algorithm. By choosing a value that promises the best performance, we then test and compare the parallel and sequential versions of the quicksort algorithm, providing us with enough data to draw a conclusion about the increase in performance when using the parallel quicksort algorithm. 
\section[{II.}]{II.} 
\section[{Quicksort}]{Quicksort}\par
Quicksort is a sorting algorithm developed by Tony Hoare that requires, on average, O(nlogn) comparisons to sort n items. In the worst case scenario, it makes O(n2) comparisons, even though this is a rare occurrence. In reality it is mostly faster than other O(nlogn) algorithms \hyperref[b0]{[1]}. The implementation of a simple sequential Quicksort algorithm follows that we choose for our needs is:\par
Choose a pivot element. We use the last element out of the sorting area Iterate through the sorting area, placing all numbers smaller then the pivot to a position on its left, while placing all other numbers to a position on its right. This is done by swapping elements.\par
The pivot is now considered to be in its sorted position and we continue with the divide-andconquer strategy, applying the same algorithm on the part to the left and the part to the right of the pivot.\par
This way, the whole, original dataset is sorted by recursively using the same algorithm on smaller and smaller parts. This is done sequentially. However, once the partitioning is done, the sorting of the new sorting areas can be performed in parallel as there is no collision.  
\section[{Related work}]{Related work}\par
Several works were done into parallel sorting algorithms. The first one, being restricted by hardware not providing multicore processors were using private1 ( D D D D ) A Values < Pivot Pivot Values > Pivot Pivot New Pivot Values < New Pivot Values > New Pivot Values > Pivot Recursive Step Initial Step\par
virtual \hyperref[b2]{[3]}. This required the solutions to communicate between them using messaging witch not only complicated the process of implementation, but also increases the overhead of parallelism. The work presented a fine-tuned parallel quick sort. The algorithm used asynchronous multiprocessors with cachecoherent shared memory. They pick the pivot using the processor with the lowest ID. Afterwards, each processor picks a blok from the left and one block from the right side of the pivot, the size of the block chosen so it can fit into the L1 cache. This two block processed in a way so that one block contains values smaller then the pivot, and the other block contains values larger or equal, with again the CPU with lowest ID performing some after-cleanup operations. Then the input array is distributed between the processors and the recursion sorting of quicksort begins until each group of processors contains only one CPU or until the size of arrays are below a limit and insertion sort is performed. Here, we found especially the idea of a threshold to use a simpler, sequential sorting algorithm to save the computational cost when sorting small arrays, especially interesting. However, in last few years, improvements in sorting have been made thanks to the works incorporating multi core and multiprocessor computer architecture \hyperref[b1]{[2]}.\par
IV. 
\section[{Theoretical analysis}]{Theoretical analysis}\par
With the parallel algorithm, we have to remember that the cost of creating, monitoring and managing of the parallel tasks is added to the total computational cost. Let's assume the average case of quicksort with computational time O(nlogn). \par
Based on Figure \hyperref[fig_1]{1} it's easy to see, that the fully developed parallel quicksort algorithm will have the shape of a binary tree.\par
For each leaf node of this tree, we will be required to perform a sequential quicksort algorithm, the size of the leaf node depending on the threshold T we choose.\par
For each node, the creation of new Tasks for child nodes will add to the total computational cost.\par
The extreme condition would be where the last leaf node would be smaller then T in case N is not divisible by T. However, this has an minimal impact on the overall performance and therefore we decided to assume, which allows us to make our theoretical analysis using a complete binary tree.\par
For a dataset of N elements, the binary tree will have N/T leaf nodes. Therefore it can be easily seen, that the tree will have nodes.\par
The number of the leaf nodes will be N/T, each of it with the size of T. This means, the computational cost to sort the leaf nodes using sequential quicksort will be With this in mind, if we would ignore any overhead, parallel quicksort would be able to provide us with this increase in performance, as shown in Figure \hyperref[fig_3]{2}. In theory, lower threshold values would provide us with even better performance. The limitation to speed increase of a parallel algorithm as compared to a sequential algorithm are the overhead caused by the need to create new, parallel processes and their management.\par
V. 
\section[{Practical analysis}]{Practical analysis}\par
For our practical analysis, we wrote a simple program to test and compare a sequential and parallel quicksort. This program first sorts a field of integers using sequential quicksort and then sorts the same field using parallel quicksort. To evaluate the overhead needed to create new tasks, we implemented a version of the quicksort algorithm, where for each recursive call, a new task is created, they are however executed not parallel but sequential.\par
Our solution was implemented in C\# as a simple form application. The window can be seen in Figure \hyperref[fig_5]{3}. 
\section[{Global Journal of Computer Science and Technology}]{Global Journal of Computer Science and Technology}\par
Volume XII Issue X Version I  From the point of user interface, the application is very simple, providing 4 items for user interaction. The first one is a textfield where wecan define the size of arrays to be used for the testing. Next is the 'Start testing' button which begins the sorting process. The last button is the Copy to clipboard button which takes the aggregated results of the tests run so far and copies them into a table structure in the clipboard, which can be easily pasted into Excel for further processing. This is the code for the public method Sort of the AbstractSort called.\par
As can be seen, a copy of the array is created so that when the other sorting algorithm is to be benchmarked, it will be benchmarked on the same, unsorted array. Afterward the current time is stored and the sorting commences. When the sorting is finished, the result time is computed as current time minus the time stored before the sorting commenced.\par
The sequential quicksort is implemented in a simple manner as the following pseudo code shows: qsort(array,left,right) Our parallel implementation is only slightly different. First, the size of the array to be sorted is checked against a threshold. If the size is smaller than the threshold, sequential quicksort is used as the overhead of creating new tasks would slow the sorting process too much. If the size of the array is bigger than the threshold, instead of calling the quicksort for each part directly, new Task is created for each of the call and let's them handle the sorting of each part of the array. This is show in the next code snippet: Last, to test the overhead caused by creating a new Task, we created a quicksort algorithm where new Task is created for the initial sorting. This is done by the following code when initializing he quicksort algorithm:\par
These algorithms were tested on the same hardware, using a quad core processor.\par
To test we used 9 randomly generated arrays of following sizes: 10; 100; 1 000; 10 000; 25 000; 50 000; 75 000; 100 000; 150 000. We did 100 separated runs, algorithms in each run using the same data, but the data being randomly generated between runs to provide variability.\par
The hardware we run our test on was a Intel Core i5 processor running at 2.53GHz. This is a dual core processor capable of running four threads in parallel. The computer had 3.8GB of memory. During the test, no other program was running to provide a interference-free environment.\par
First, by using a trial and error approach, we established a suitable value for the SEQ\textunderscore THRESHOLD value to be 1000. We ran a full scale test on arrays of 9 different sizes with three different SEQ\textunderscore THRESHOLD values, 1000,5000 and 50 000. The resulting times can be seen in Table \hyperref[tab_1]{1} and in Figure 5.  With the threshold set at 50000, the parallel algorithm is actually slower, as the computational cost of creating new tasks increases the total run time, but the parallelism is not utilized enough to offset this. In Figure 6 it can be clearly seen, that with the higher threshold of 50000, the additional computation cost of creating new threads cannot be compensated for by doing parallel computation as the algorithm returns to sequential quicksorting too soon.    This graph was created by using the formula\par
As can be seen here, at low number of elements no speed up is achieved. As the number of elements increases, the speed of sorting actually decreases. This is caused as stated before by the overhead needed for creating the parallel tasks and as there is not enough elements for the parallelism being able to compensate for this. After the number of elements increases enough, the overall speed and speed gain increases as well by about 20\%. 
\section[{VI.}]{VI.} 
\section[{Conclusion}]{Conclusion}\par
We successfully implemented a parallel version of quicksort algorithm. After choosing a appropriate threshold value to switch from parallel to sequential sorting, we observed the performance of the algorithm. The results are obviously in favor of the parallel quicksort algorithm. Using a reasonable threshold to return to sequential quicksort, we are able to circumvent the increased computational cost of creating new tasks for small datasets, while with the bigger datasets we take advantage of the parallelism possible by today's hardware. And thanks to simplicity of the parallel implementation of quicksort algorithm it is easy to achieve major, 20\% increase of performance when sorting a larger dataset. \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-2.png}
\caption{\label{fig_0}}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{1}\includegraphics[]{image-3.png}
\caption{\label{fig_1}Figure 1 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-4.png}
\caption{\label{fig_2}}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{2}\includegraphics[]{image-5.png}
\caption{\label{fig_3}Figure 2 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-6.png}
\caption{\label{fig_4}}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{3}\includegraphics[]{image-7.png}
\caption{\label{fig_5}Figure 3 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{4}\includegraphics[]{image-8.png}
\caption{\label{fig_6}Figure 4 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-9.png}
\caption{\label{fig_7}}\end{figure}
      \begin{figure}[htbp]
\noindent\textbf{1} \par 
\begin{longtable}{}
\end{longtable} \par
 
\caption{\label{tab_1}Table 1 :}\end{figure}
 			\footnote{© 2012 Global Journals Inc. (US)} 			\footnote{© 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology} 		 		\backmatter  			  				\begin{bibitemlist}{1}
\bibitem[Chengyan ()]{b2}\label{b2} 	 		 			Z Chengyan 		.  		\textit{Parallel Quick sort algorithm with PVM optimization},  				1996.  	 
\bibitem[Tsigas et al.]{b1}\label{b1} 	 		\textit{Fast Parallel Implementation of Quicksort and its Performance Evaluation on SUN Enterprise 10000},  		 			P Tsigas 		,  		 			Y Zhang 		,  		 			Simple 		.  		 	 
\bibitem[Skiena ()]{b0}\label{b0} 	 		\textit{The Algorithm Design Manual, Second Edition},  		 			S S Skiena 		.  		2008. Springer. p. 129.  	 
\end{bibitemlist}
 			 		 	 
\end{document}
