src/gbpLib/gbpSort/merge_sort.c
void merge_helper(void *       data,
                  size_t *     index,
                  size_t       left,
                  size_t       right,
                  void *       scratch_d,
                  size_t *     scratch_i,
                  SID_Datatype data_type,
                  int          flag_compute_index) {
    // left is the index of the leftmost element of the subarray; right is one
    //   past the index of the rightmost element
    size_t length            = right - left;
    size_t midpoint_distance = length / 2;
    size_t l = left, r = left + midpoint_distance;
    size_t i = 0;
    // base case: one element
    if(right == left + 1)
        return;
    else {
        // sort each (left and right) subarray
        merge_helper(data, index, left, left + midpoint_distance, scratch_d, scratch_i, data_type, flag_compute_index);
        merge_helper(data, index, left + midpoint_distance, right, scratch_d, scratch_i, data_type, flag_compute_index);

        // merge the arrays together using scratch for temporary storage
        for(i = 0; i < length; i++) {
            // Check to see if any elements remain in the left array; if so,
            //   we check if there are any elements left in the right array; if
            //   so, we compare them.  Otherwise, we know that the merge must
            //   use the element from the left array.  Then, we copy the
            //   sorted subarray back into the input data.
            if(data_type == SID_INT) {
                if(l < left + midpoint_distance && (r == right || (((int *)data)[l] <= ((int *)data)[r]))) {
                    ((int *)scratch_d)[i] = ((int *)data)[l];
                    if(flag_compute_index)
                        scratch_i[i] = index[l];
                    l++;
                } else {
                    ((int *)scratch_d)[i] = ((int *)data)[r];
                    if(flag_compute_index)
                        scratch_i[i] = index[r];
                    r++;
                }
            } else if(data_type == SID_SIZE_T) {
                if(l < left + midpoint_distance && (r == right || (((size_t *)data)[l] <= ((size_t *)data)[r]))) { //*
                    ((size_t *)scratch_d)[i] = ((size_t *)data)[l];
                    if(flag_compute_index)
                        scratch_i[i] = index[l];
                    l++;
                } else {
                    ((size_t *)scratch_d)[i] = ((size_t *)data)[r];
                    if(flag_compute_index)
                        scratch_i[i] = index[r];
                    r++;
                }
            } else if(data_type == SID_FLOAT) {
                if(l < left + midpoint_distance && (r == right || (((float *)data)[l] <= ((float *)data)[r]))) {
                    ((float *)scratch_d)[i] = ((float *)data)[l];
                    if(flag_compute_index)
                        scratch_i[i] = index[l];
                    l++;
                } else {
                    ((float *)scratch_d)[i] = ((float *)data)[r];
                    if(flag_compute_index)
                        scratch_i[i] = index[r];
                    r++;
                }
            } else if(data_type == SID_DOUBLE) {
                if(l < left + midpoint_distance && (r == right || (((double *)data)[l] <= ((double *)data)[r]))) {
                    ((double *)scratch_d)[i] = ((double *)data)[l];
                    if(flag_compute_index)
                        scratch_i[i] = index[l];
                    l++;
                } else {
                    ((double *)scratch_d)[i] = ((double *)data)[r];
                    if(flag_compute_index)
                        scratch_i[i] = index[r];
                    r++;
                }
            }
        }
    }
    if(data_type == SID_INT) {
        for(i = left; i < right; i++) {
            ((int *)data)[i] = ((int *)scratch_d)[i - left];
            if(flag_compute_index)
                index[i] = scratch_i[i - left];
        }
    } else if(data_type == SID_SIZE_T) {
        for(i = left; i < right; i++) {
            ((size_t *)data)[i] = ((size_t *)scratch_d)[i - left];
            if(flag_compute_index)
                index[i] = scratch_i[i - left];
        }
    } else if(data_type == SID_FLOAT) {
        for(i = left; i < right; i++) {
            ((float *)data)[i] = ((float *)scratch_d)[i - left];
            if(flag_compute_index)
                index[i] = scratch_i[i - left];
        }
    } else if(data_type == SID_DOUBLE) {
        for(i = left; i < right; i++) {
            ((double *)data)[i] = ((double *)scratch_d)[i - left];
            if(flag_compute_index)
                index[i] = scratch_i[i - left];
        }
    }
}
// This is the main recursive routine for the merge sort
This is the main recursive routine for the merge sort
This is the main recursive routine for the merge sort
void merge_helper(void *       data,
                  size_t *     index,
                  size_t       left,
                  size_t       right,
                  void *       scratch_d,
                  size_t *     scratch_i,
                  SID_Datatype data_type,
                  int          flag_compute_index) {
    size_t length            = right - left;
    size_t midpoint_distance = length / 2;
    size_t l = left, r = left + midpoint_distance;
    size_t i = 0;
    if(right == left + 1)
        return;
    else {
        merge_helper(data, index, left, left + midpoint_distance, scratch_d, scratch_i, data_type, flag_compute_index);
        merge_helper(data, index, left + midpoint_distance, right, scratch_d, scratch_i, data_type, flag_compute_index);
        for(i = 0; i < length; i++) {
            if(data_type == SID_INT) {
                if(l < left + midpoint_distance && (r == right || (((int *)data)[l] <= ((int *)data)[r]))) {
                    ((int *)scratch_d)[i] = ((int *)data)[l];
                    if(flag_compute_index)
                        scratch_i[i] = index[l];
                    l++;
                } else {
                    ((int *)scratch_d)[i] = ((int *)data)[r];
                    if(flag_compute_index)
                        scratch_i[i] = index[r];
                    r++;
                }
            } else if(data_type == SID_SIZE_T) {
                if(l < left + midpoint_distance && (r == right || (((size_t *)data)[l] <= ((size_t *)data)[r]))) { 
                    ((size_t *)scratch_d)[i] = ((size_t *)data)[l];
                    if(flag_compute_index)
                        scratch_i[i] = index[l];
                    l++;
                } else {
                    ((size_t *)scratch_d)[i] = ((size_t *)data)[r];
                    if(flag_compute_index)
                        scratch_i[i] = index[r];
                    r++;
                }
            } else if(data_type == SID_FLOAT) {
                if(l < left + midpoint_distance && (r == right || (((float *)data)[l] <= ((float *)data)[r]))) {
                    ((float *)scratch_d)[i] = ((float *)data)[l];
                    if(flag_compute_index)
                        scratch_i[i] = index[l];
                    l++;
                } else {
                    ((float *)scratch_d)[i] = ((float *)data)[r];
                    if(flag_compute_index)
                        scratch_i[i] = index[r];
                    r++;
                }
            } else if(data_type == SID_DOUBLE) {
                if(l < left + midpoint_distance && (r == right || (((double *)data)[l] <= ((double *)data)[r]))) {
                    ((double *)scratch_d)[i] = ((double *)data)[l];
                    if(flag_compute_index)
                        scratch_i[i] = index[l];
                    l++;
                } else {
                    ((double *)scratch_d)[i] = ((double *)data)[r];
                    if(flag_compute_index)
                        scratch_i[i] = index[r];
                    r++;
                }
            }
        }
    }
    if(data_type == SID_INT) {
        for(i = left; i < right; i++) {
            ((int *)data)[i] = ((int *)scratch_d)[i - left];
            if(flag_compute_index)
                index[i] = scratch_i[i - left];
        }
    } else if(data_type == SID_SIZE_T) {
        for(i = left; i < right; i++) {
            ((size_t *)data)[i] = ((size_t *)scratch_d)[i - left];
            if(flag_compute_index)
                index[i] = scratch_i[i - left];
        }
    } else if(data_type == SID_FLOAT) {
        for(i = left; i < right; i++) {
            ((float *)data)[i] = ((float *)scratch_d)[i - left];
            if(flag_compute_index)
                index[i] = scratch_i[i - left];
        }
    } else if(data_type == SID_DOUBLE) {
        for(i = left; i < right; i++) {
            ((double *)data)[i] = ((double *)scratch_d)[i - left];
            if(flag_compute_index)
                index[i] = scratch_i[i - left];
        }
    }
}
void merge_helper ( void * data , size_t * index , size_t left , size_t right , void * scratch_d , size_t * scratch_i , SID_Datatype data_type , int flag_compute_index ) { size_t length = right - left ; size_t midpoint_distance = length / 2 ; size_t l = left , r = left + midpoint_distance ; size_t i = 0 ; if ( right == left + 1 ) return ; else { merge_helper ( data , index , left , left + midpoint_distance , scratch_d , scratch_i , data_type , flag_compute_index ) ; merge_helper ( data , index , left + midpoint_distance , right , scratch_d , scratch_i , data_type , flag_compute_index ) ; for ( i = 0 ; i < length ; i ++ ) { if ( data_type == SID_INT ) { if ( l < left + midpoint_distance && ( r == right || ( ( ( int * ) data ) [ l ] <= ( ( int * ) data ) [ r ] ) ) ) { ( ( int * ) scratch_d ) [ i ] = ( ( int * ) data ) [ l ] ; if ( flag_compute_index ) scratch_i [ i ] = index [ l ] ; l ++ ; } else { ( ( int * ) scratch_d ) [ i ] = ( ( int * ) data ) [ r ] ; if ( flag_compute_index ) scratch_i [ i ] = index [ r ] ; r ++ ; } } else if ( data_type == SID_SIZE_T ) { if ( l < left + midpoint_distance && ( r == right || ( ( ( size_t * ) data ) [ l ] <= ( ( size_t * ) data ) [ r ] ) ) ) { ( ( size_t * ) scratch_d ) [ i ] = ( ( size_t * ) data ) [ l ] ; if ( flag_compute_index ) scratch_i [ i ] = index [ l ] ; l ++ ; } else { ( ( size_t * ) scratch_d ) [ i ] = ( ( size_t * ) data ) [ r ] ; if ( flag_compute_index ) scratch_i [ i ] = index [ r ] ; r ++ ; } } else if ( data_type == SID_FLOAT ) { if ( l < left + midpoint_distance && ( r == right || ( ( ( float * ) data ) [ l ] <= ( ( float * ) data ) [ r ] ) ) ) { ( ( float * ) scratch_d ) [ i ] = ( ( float * ) data ) [ l ] ; if ( flag_compute_index ) scratch_i [ i ] = index [ l ] ; l ++ ; } else { ( ( float * ) scratch_d ) [ i ] = ( ( float * ) data ) [ r ] ; if ( flag_compute_index ) scratch_i [ i ] = index [ r ] ; r ++ ; } } else if ( data_type == SID_DOUBLE ) { if ( l < left + midpoint_distance && ( r == right || ( ( ( double * ) data ) [ l ] <= ( ( double * ) data ) [ r ] ) ) ) { ( ( double * ) scratch_d ) [ i ] = ( ( double * ) data ) [ l ] ; if ( flag_compute_index ) scratch_i [ i ] = index [ l ] ; l ++ ; } else { ( ( double * ) scratch_d ) [ i ] = ( ( double * ) data ) [ r ] ; if ( flag_compute_index ) scratch_i [ i ] = index [ r ] ; r ++ ; } } } } if ( data_type == SID_INT ) { for ( i = left ; i < right ; i ++ ) { ( ( int * ) data ) [ i ] = ( ( int * ) scratch_d ) [ i - left ] ; if ( flag_compute_index ) index [ i ] = scratch_i [ i - left ] ; } } else if ( data_type == SID_SIZE_T ) { for ( i = left ; i < right ; i ++ ) { ( ( size_t * ) data ) [ i ] = ( ( size_t * ) scratch_d ) [ i - left ] ; if ( flag_compute_index ) index [ i ] = scratch_i [ i - left ] ; } } else if ( data_type == SID_FLOAT ) { for ( i = left ; i < right ; i ++ ) { ( ( float * ) data ) [ i ] = ( ( float * ) scratch_d ) [ i - left ] ; if ( flag_compute_index ) index [ i ] = scratch_i [ i - left ] ; } } else if ( data_type == SID_DOUBLE ) { for ( i = left ; i < right ; i ++ ) { ( ( double * ) data ) [ i ] = ( ( double * ) scratch_d ) [ i - left ] ; if ( flag_compute_index ) index [ i ] = scratch_i [ i - left ] ; } } }
This is the main recursive routine for the merge sort
This is the main recursive routine for the merge sort
// left is the index of the leftmost element of the subarray; right is one //   past the index of the rightmost element // base case: one element // sort each (left and right) subarray // merge the arrays together using scratch for temporary storage // Check to see if any elements remain in the left array; if so, //   we check if there are any elements left in the right array; if //   so, we compare them.  Otherwise, we know that the merge must //   use the element from the left array.  Then, we copy the //   sorted subarray back into the input data. //*