Mastering Algorithms With C - Kyle Loudon [138]
if ((m = (char *)malloc(esize * ((k - i) + 1))) == NULL)
return -1;
/*****************************************************************************
* *
* Continue while either division has elements to merge. *
* *
*****************************************************************************/
while (ipos <= j || jpos <= k) {
if (ipos > j) {
/***********************************************************************
* *
* The left division has no more elements to merge. *
* *
***********************************************************************/
while (jpos <= k) {
memcpy(&m[mpos * esize], &a[jpos * esize], esize);
jpos++;
mpos++;
}
continue;
}
else if (jpos > k) {
/***********************************************************************
* *
* The right division has no more elements to merge. *
* *
***********************************************************************/
while (ipos <= j) {
memcpy(&m[mpos * esize], &a[ipos * esize], esize);
ipos++;
mpos++;
}
continue;
}
/**************************************************************************
* *
* Append the next ordered element to the merged elements. *
* *
**************************************************************************/
if (compare(&a[ipos * esize], &a[jpos * esize]) < 0) {
memcpy(&m[mpos * esize], &a[ipos * esize], esize);
ipos++;
mpos++;
}
else {
memcpy(&m[mpos * esize], &a[jpos * esize], esize);
jpos++;
mpos++;
}
}
/*****************************************************************************
* *
* Prepare to pass back the merged data. *
* *
*****************************************************************************/
memcpy(&a[i * esize], m, esize * ((k - i) + 1));
/*****************************************************************************
* *
* Free the storage allocated for merging. *
* *
*****************************************************************************/
free(m);
return 0;
}
/*****************************************************************************
* *
* -------------------------------- mgsort -------------------------------- *
* *
*****************************************************************************/
int mgsort(void *data, int esize, int i, int k, int (*compare)
(const void *key1, const void *key2)) {
int j;
/*****************************************************************************
* *
* Stop the recursion when no more divisions can be made. *
* *
*****************************************************************************/
if (i < k) {
/**************************************************************************
* *
* Determine where to divide the elements. *
* *
**************************************************************************/
j = (int)(((i + k - 1)) / 2);
/**************************************************************************
* *
* Recursively sort the two divisions. *
* *
**************************************************************************/
if (mgsort(data, size, esize, i, j, compare) < 0)
return -1;
if (mgsort(data, size, esize, j + 1, k, compare) < 0)
return -1;
/**************************************************************************
* *
* Merge the two sorted divisions into a single sorted set. *
* *
**************************************************************************/
if (merge(data, esize, i, j, k, compare) < 0)
return -1;
}
return
0;
}
Description of Counting Sort
Counting sort is an efficient, linear-time sorting algorithm that works by counting how many times each element of a set occurs to determine how the set should be ordered. By avoiding the comparisons that have been a part of the sorting methods presented thus far, counting sort improves on the O (n lg n) runtime bound of comparison sorts.
Counting sort does have some limitations. The most significant is that it works only with integers or data that can be expressed in some integer form. This is because counting sort makes use