hello,
I am running a merge sort routine on an array of numbers. My intention is not to output the sorted array but to reorder the indices of the array so that they reflect the sorted order (descending). For example, if the array were {2, 7, 4}, my indices would be {1,2,0}. Thus I need to update the identity map {0,1,2} to {1,2,0}. I store this map as a vector of ints. I feed the array of numbers and an iterator pointing to the first element of the map-vector as well as the array-size to the merge-sort subroutine. I first call mergeSort(...) which calls m_sort(....) which calls itself and merge(...).
Identifiers used and their meaning:
numbers: array of numbers to sort
fn : map array (doesn't appear in code)
fn_ptr: iterator on venctor<int> that points to the first element of the
map vector
left : first index of range to sort
right: last index of range to sort
----
void merge(double numbers[], vector<int>::iterator fn_ptr, int left, int mid, int right);
void mergeSort(double numbers[],vector<int>::iterator fn_ptr, int array_size)
{
m_sort(numbers, fn_ptr, 0, array_size - 1);
}
void m_sort(double numbers[], vector<int>::iterator fn_ptr, int left, int right)
{
int mid;
vector<int>::iterator dum_ptr;
if (right > left)
{
mid = (right + left) / 2;
//recursive call to sort two contiguous subsets
m_sort(numbers, fn_ptr, left, mid);
m_sort(numbers, fn_ptr+mid-left+1, (mid+1), right);
//merge sorted subsets
merge(numbers, fn_ptr, fn_ptr+mid-left+1, left, (mid+1), right);
}
}
void merge(double numbers[], vector<int>::iterator fn_ptr_1, vector<int>::iterator fn_ptr_2, int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
int N_cp=sizeof(numbers);
vector<int> fn_dum(N_cp);
vector<int>::iterator dum_ptr=fn_ptr_1;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
int left_dum=left;
while ((left <= left_end) && (mid <= right))
{
if (numbers[*fn_ptr_1] >= numbers[*fn_ptr_2])
{
fn_dum[tmp_pos] = *fn_ptr_1;
tmp_pos += 1;
left ++;
++fn_ptr_1;
}
else
{
fn_dum[tmp_pos] = *fn_ptr_2;
tmp_pos += 1;
mid += 1;
++fn_ptr_2;
}
}
while (left <= left_end)
{
fn_dum[tmp_pos] = *fn_ptr_1;
left += 1;
++fn_ptr_1;
tmp_pos += 1;
}
while (mid <= right)
{
fn_dum[tmp_pos] = *fn_ptr_2;
mid += 1;
++fn_ptr_2;
tmp_pos += 1;
}
//update fn using fn_dum
for (i=0; i < num_elements; i++)
{
*dum_ptr = fn_dum[left_dum];
left_dum++;
++dum_ptr;
}
fn_dum.clear();
cout << "End of merge." << endl;
cout << endl;
}------
I call the mergeSort as
mergeSort(numbers, fn_ptr,array_size).
In the example above, numbers = {2,7,4}. I create fn={0,1,2} as a vector<int>, and then set fn_ptr=fn.begin(). Then, I call
mergeSort(numbers,fn_ptr,3).
Note that in any call, fn_ptr points to the value of fn at the first index in the range to be sorted.
In my implementation, array_size=100. I get the "glibc detected" error inside m_sort(numbers,fn_ptr,10,12), at the point where msort(.,.,10,11) has completed and msort(.,.,12,12) is about to be called.
thanks for any help. Glad to provide more info to clarify.
Tara