/**
 * File: SortUtil.h
 */

#pragma once


template< typename T >
int Compare( T items1[], int first1, T items2[], int first2, int length ) {
    int result = 0;        
    for ( int i = 0; i < length; ++i ) {
        if ( items1[ first1 + i ] < items2[ first2 + i ] ) {
            result = -1;
            break;
        }
        else if ( items2[ first2 + i ] < items1[ first1 + i ] ) {
            result = +1;
            break;
        }
    }
    return result;
}


template< typename T >
bool IsSorted( T items[], int first, int last ) {
    bool isSorted = true;
    for ( int i = first; i < last; ++i ) {
        if ( items[ i + 1 ] < items[ i ] ) {
            isSorted = false;
            break;
        }
    }
    return isSorted;
}


template< typename T >
int Partition( T items[], int first, int last, T pivot ) {
    int j = first - 1;
    for ( int i = first; i <= last; ++i )    {
        if ( items[ i ] < pivot ) {
            std::swap( items[ ++j ], items[ i ] );
        }
    }
    return j;
}


template< typename T >
int PartitionByIndex( T items[], int first, int last, int index ) {
    std::swap( items[ index ], items[ last ] );
    int i = 1 + Partition( items, first, last, items[ last ] );
    std::swap( items[ i ], items[ last ] );
    return i;
}


template< typename T >
void Select( T items[], int first, int last, int index ) {
    int i = PartitionByIndex( items, first, last, ( first + last ) / 2 );
    if ( i > index ) {
        Select( items, first, i - 1, index );        
    }
    else if ( i < index ) {        
        Select( items, i + 1, last, index );    
    }
}

/**
 * File: QuickSort.h
 */

#pragma once
#include "SortUtil.h"
#include <iostream>


template< typename T >
void QuickSort( T items[], int first, int last ) {        
    int i = PartitionByIndex( items, first, last, ( first + last ) / 2 );        
    if ( i - 1 > first ) { 
        QuickSort( items, first, i - 1 ); 
    }
    if ( i + 1 < last ) { 
        QuickSort( items, i + 1, last ); 
    }
}    

/**
 * File: QuickSort_OpenMP.h
 */

#pragma once
#include "SortUtil.h"
#include "QuickSort.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <omp.h>


template< typename T >
void QuickSort_OpenMP( T items[], int first, int last ) {        
    int maxDeep = (int)( ceil( log( (double)omp_get_num_procs() ) / log( 2.0 ) ) );
    QuickSort_OpenMP( items, first, last, 0, maxDeep );
}    


template< typename T >
void QuickSort_OpenMP( T items[], int first, int last, int deep, int maxDeep ) {
    if ( deep >= maxDeep ) {
        QuickSort( items, first, last );
    }
    else {
        int i = ( first + last ) / 2;        
        Select( items, first, last, i );
        
        #pragma omp parallel
        {
            #pragma omp sections nowait
            {
                #pragma omp section
                if ( i - 1 > first ) {
                    QuickSort_OpenMP( items, first, i - 1, deep + 1, maxDeep );
                }
                #pragma omp section
                if ( i + 1 < last ) { 
                    QuickSort_OpenMP( items, i + 1, last, deep + 1, maxDeep ); 
                }
            }    
        }
    }
}