src/gbpLib/gbpSort/merge_sort.c
void merge_sort(void *data_in, size_t n_data, size_t **index, SID_Datatype data_type, int flag_compute_index, int flag_in_place) {
    size_t  i, j;
    void *  data_sort;
    void *  scratch_d;
    size_t *scratch_i;
    size_t  data_size;
    size_t *idx_sort;
    int     flag_compute_index_sort;

    // Process passed arguments:
    //   Determine data element size
    if(data_type == SID_INT)
        data_size = sizeof(int);
    else if(data_type == SID_SIZE_T)
        data_size = sizeof(size_t);
    else if(data_type == SID_FLOAT)
        data_size = sizeof(float);
    else if(data_type == SID_DOUBLE)
        data_size = sizeof(double);
    else if(data_type == SID_LONG_LONG)
        data_size = sizeof(long long);
    else
        SID_exit_error("Unsupported data type {%d}", SID_ERROR_LOGIC, data_type);

    // Allocate scratch space and sort indices (if needed)
    scratch_d = SID_malloc(data_size * n_data);
    if(flag_in_place == SORT_COMPUTE_INPLACE)
        data_sort = data_in;
    else if(flag_in_place == SORT_COMPUTE_NOT_INPLACE) {
        data_sort = SID_malloc(data_size * n_data);
        memcpy(data_sort, data_in, data_size * n_data);
    } else {
        fprintf(stderr, "ERROR (merge_sort): flag_in_place {%d} must be SORT_COMPUTE_INPLACE||SORT_COMPUTE_NOT_INPLACE\n", flag_in_place);
    }
    flag_compute_index_sort = GBP_FALSE;
    if(flag_compute_index == SORT_COMPUTE_INDEX || flag_compute_index == SORT_COMPUTE_RANK) {
        flag_compute_index_sort = GBP_TRUE;
        scratch_i               = (size_t *)SID_malloc(sizeof(size_t) * n_data);
        idx_sort                = (size_t *)SID_malloc(sizeof(size_t) * n_data);
        for(i = 0; i < n_data; i++)
            idx_sort[i] = i;
    } else if(flag_compute_index != SORT_INPLACE_ONLY) {
        fprintf(stderr,
                "ERROR (merge_sort): flag_compute_index {%d} must be SORT_COMPUTE_INDEX||SORT_COMPUTE_RANK||SORT_INPLACE_ONLY\n",
                flag_compute_index);
    }

    // Check for nonsensical flag combinations
    if(flag_in_place == SORT_COMPUTE_NOT_INPLACE && flag_compute_index == SORT_INPLACE_ONLY)
        fprintf(stderr, "ERROR (mege_sort): flag combinations will generate no results.\n");

    // Perform the sort
    if(n_data > 0)
        merge_helper(data_sort, idx_sort, 0, n_data, scratch_d, scratch_i, data_type, flag_compute_index_sort);
    SID_free((void **)&(scratch_d));
    if(flag_compute_index_sort)
        SID_free((void **)&scratch_i);
    if(flag_in_place == SORT_COMPUTE_NOT_INPLACE)
        SID_free((void **)&data_sort);

    // Invert sort indices to produce ranks (if needed)
    if(flag_compute_index == SORT_COMPUTE_RANK && n_data > 0) {
        merge_sort(idx_sort, n_data, index, SID_SIZE_T, SORT_COMPUTE_INDEX, SORT_COMPUTE_INPLACE);
        SID_free((void **)&idx_sort);
    } else if(flag_compute_index == SORT_COMPUTE_INDEX)
        (*index) = idx_sort;
}
// This sort routine is RAM-inefficient, but it is STABLE ... used
//  when computing a distributed rank-list
This sort routine is RAM-inefficient, but it is STABLE ... used
when computing a distributed rank-list
This sort routine is RAM - inefficient but it is STABLE ... used when computing a distributed rank - list
void merge_sort(void *data_in, size_t n_data, size_t **index, SID_Datatype data_type, int flag_compute_index, int flag_in_place) {
    size_t  i, j;
    void *  data_sort;
    void *  scratch_d;
    size_t *scratch_i;
    size_t  data_size;
    size_t *idx_sort;
    int     flag_compute_index_sort;
    if(data_type == SID_INT)
        data_size = sizeof(int);
    else if(data_type == SID_SIZE_T)
        data_size = sizeof(size_t);
    else if(data_type == SID_FLOAT)
        data_size = sizeof(float);
    else if(data_type == SID_DOUBLE)
        data_size = sizeof(double);
    else if(data_type == SID_LONG_LONG)
        data_size = sizeof(long long);
    else
        SID_exit_error("Unsupported data type {%d}", SID_ERROR_LOGIC, data_type);
    scratch_d = SID_malloc(data_size * n_data);
    if(flag_in_place == SORT_COMPUTE_INPLACE)
        data_sort = data_in;
    else if(flag_in_place == SORT_COMPUTE_NOT_INPLACE) {
        data_sort = SID_malloc(data_size * n_data);
        memcpy(data_sort, data_in, data_size * n_data);
    } else {
        fprintf(stderr, "ERROR (merge_sort): flag_in_place {%d} must be SORT_COMPUTE_INPLACE||SORT_COMPUTE_NOT_INPLACE\n", flag_in_place);
    }
    flag_compute_index_sort = GBP_FALSE;
    if(flag_compute_index == SORT_COMPUTE_INDEX || flag_compute_index == SORT_COMPUTE_RANK) {
        flag_compute_index_sort = GBP_TRUE;
        scratch_i               = (size_t *)SID_malloc(sizeof(size_t) * n_data);
        idx_sort                = (size_t *)SID_malloc(sizeof(size_t) * n_data);
        for(i = 0; i < n_data; i++)
            idx_sort[i] = i;
    } else if(flag_compute_index != SORT_INPLACE_ONLY) {
        fprintf(stderr,
                "ERROR (merge_sort): flag_compute_index {%d} must be SORT_COMPUTE_INDEX||SORT_COMPUTE_RANK||SORT_INPLACE_ONLY\n",
                flag_compute_index);
    }
    if(flag_in_place == SORT_COMPUTE_NOT_INPLACE && flag_compute_index == SORT_INPLACE_ONLY)
        fprintf(stderr, "ERROR (mege_sort): flag combinations will generate no results.\n");
    if(n_data > 0)
        merge_helper(data_sort, idx_sort, 0, n_data, scratch_d, scratch_i, data_type, flag_compute_index_sort);
    SID_free((void **)&(scratch_d));
    if(flag_compute_index_sort)
        SID_free((void **)&scratch_i);
    if(flag_in_place == SORT_COMPUTE_NOT_INPLACE)
        SID_free((void **)&data_sort);
    if(flag_compute_index == SORT_COMPUTE_RANK && n_data > 0) {
        merge_sort(idx_sort, n_data, index, SID_SIZE_T, SORT_COMPUTE_INDEX, SORT_COMPUTE_INPLACE);
        SID_free((void **)&idx_sort);
    } else if(flag_compute_index == SORT_COMPUTE_INDEX)
        (*index) = idx_sort;
}
void merge_sort ( void * data_in , size_t n_data , size_t * * index , SID_Datatype data_type , int flag_compute_index , int flag_in_place ) { size_t i , j ; void * data_sort ; void * scratch_d ; size_t * scratch_i ; size_t data_size ; size_t * idx_sort ; int flag_compute_index_sort ; if ( data_type == SID_INT ) data_size = sizeof ( int ) ; else if ( data_type == SID_SIZE_T ) data_size = sizeof ( size_t ) ; else if ( data_type == SID_FLOAT ) data_size = sizeof ( float ) ; else if ( data_type == SID_DOUBLE ) data_size = sizeof ( double ) ; else if ( data_type == SID_LONG_LONG ) data_size = sizeof ( long long ) ; else SID_exit_error ( " " , SID_ERROR_LOGIC , data_type ) ; scratch_d = SID_malloc ( data_size * n_data ) ; if ( flag_in_place == SORT_COMPUTE_INPLACE ) data_sort = data_in ; else if ( flag_in_place == SORT_COMPUTE_NOT_INPLACE ) { data_sort = SID_malloc ( data_size * n_data ) ; memcpy ( data_sort , data_in , data_size * n_data ) ; } else { fprintf ( stderr , " \n " , flag_in_place ) ; } flag_compute_index_sort = GBP_FALSE ; if ( flag_compute_index == SORT_COMPUTE_INDEX || flag_compute_index == SORT_COMPUTE_RANK ) { flag_compute_index_sort = GBP_TRUE ; scratch_i = ( size_t * ) SID_malloc ( sizeof ( size_t ) * n_data ) ; idx_sort = ( size_t * ) SID_malloc ( sizeof ( size_t ) * n_data ) ; for ( i = 0 ; i < n_data ; i ++ ) idx_sort [ i ] = i ; } else if ( flag_compute_index != SORT_INPLACE_ONLY ) { fprintf ( stderr , " \n " , flag_compute_index ) ; } if ( flag_in_place == SORT_COMPUTE_NOT_INPLACE && flag_compute_index == SORT_INPLACE_ONLY ) fprintf ( stderr , " \n " ) ; if ( n_data > 0 ) merge_helper ( data_sort , idx_sort , 0 , n_data , scratch_d , scratch_i , data_type , flag_compute_index_sort ) ; SID_free ( ( void * * ) & ( scratch_d ) ) ; if ( flag_compute_index_sort ) SID_free ( ( void * * ) & scratch_i ) ; if ( flag_in_place == SORT_COMPUTE_NOT_INPLACE ) SID_free ( ( void * * ) & data_sort ) ; if ( flag_compute_index == SORT_COMPUTE_RANK && n_data > 0 ) { merge_sort ( idx_sort , n_data , index , SID_SIZE_T , SORT_COMPUTE_INDEX , SORT_COMPUTE_INPLACE ) ; SID_free ( ( void * * ) & idx_sort ) ; } else if ( flag_compute_index == SORT_COMPUTE_INDEX ) ( * index ) = idx_sort ; }
This sort routine is RAM-inefficient, but it is STABLE ... used
when computing a distributed rank-list
This sort routine is RAM - inefficient but it is STABLE ... used when computing a distributed rank - list
// Process passed arguments: //   Determine data element size // Allocate scratch space and sort indices (if needed) // Check for nonsensical flag combinations // Perform the sort // Invert sort indices to produce ranks (if needed)