/* * MSORT.C version 1.0 18-Nov-1986 * * A general-purpose implementation of a merge-sort for linked lists. * * Written for the Commodore Amiga 1000, version 1.1 * using Lattice C v3.03 by Davide P. Cervone * * The merge-sort algorithm takes advantage of the fact that it is * easy to combine two sorted lists into one sorted list: just keep * taking the smaller item off the top of the two lists and add it * to the bottom of the new list until the original lists are empty. * * The sort algorithm first places each item to be sorted in its * own list (one item long). Pairs of these singleton lists are merged * in the manner described above, and we are left with half as many lists * as before, each two items long. Pairs of these lists are combined to * form half as many lists again, each four items long. This process is * repeated until only one list remains. This is the final, sorted list. * * The merge-sort is ideal for linked lists, since it does not require * random access look-ups (which are difficult in linked-lists). It does * not require extra "work-space", so no memory is wasted. Finally, its * result is a simple, linked-list structure, ready to use (unlike some sort * methods that result in trees or other structures were it is dificult to * get from one item to the next). * * The merge-sort is fairly efficient. In it's worst case, it takes * n * (log(n) - 1) + 1 comparisons to sort n items (where the log() * function is the log to base 2). Thus, for 1024 items, the maximum * number of comparisons is 1024*(10-1)+1 = 9217, or approximately 9 * comparisons per item. And that's its worst case! Compare this to * a worst case of n*(n-1)/2 for some popular sorts (e.g., the tree sort). * The worst case for the tree sort for 1024 items is 523776 compares! * * In its best case, the merge-sort takes n * log(n) / 2 comparisons. * For our example of n=1024, that's 5120 comparisons. For the tree sort, * the minimum is approximately n * (log(n) - 2) comparisons, for a * minimum of 8192 comparisons for 1024 items. * * Note that the maximum comparisons that will ever occur with the merge-sort * is no more than n more than the minimum number possible with the tree * sort. * * While these numbers look impressive, there is one drawback: the merge- * sort is heavily weighted toward its worst case, since the merge sort skips * comparisons only when one list runs out of items more than one item before * the other. In practice, the average number of comparisons made by the * merge-sort is a consistant 96% of the maximum number. This gives you a very * acurate estimate of the number of comparisons (hence the time it takes) to * sort a list of a particular size. Since the maximum value is so close to * the most probable value, you don't have to worry about pathelogic cases * slowing down your sort routine (for a tree sort, the "pathelogic" case * is a pre-sorted list, which may not be an uncommon case). * * In a comparison against the tree sort using random data (the kind the * tree sort handles best), the merge-sort was found to take 96% of its * maximum number of sorts, while the tree sort averaged about 38% more than * it's minimum (there was considerably more variation with the tree sort). * Overall, the tree sort was found to take a consitant 25% more comparisons * than the merge-sort on lists of length 300 items to 10000 items. For * 100 items, the difference drops off to about 15%, and for 10 items, the two * sorts are about the same, with the merge-sort comming out a little bit * ahead (one or two comparisons out of an average of 23). * * All in all, the merge-sort is an effective, fast, and very useful sort * that compares favorably with other sort algorithms. */ #include #define ADD_TO_NEWLIST(l) (newlist = (newlist->Next = l)) /* * The linked list is a double-linked list (there are pointers to both * the previous and the following item). The end of the list is marked * by NULL pointers. * * The pointers should appear at the top of the structure you intend to * sort, so if you are sorting a linked list of people's names, you might * use a structure like the following in your main program: * * struct ListItem * { * struct ListItem *Next; * struct ListItem *Prev; * char FirstName[30]; * char MiddleInitial; * char LastName[50] * }; * * The pointers must be the first fields so that mSort() and Merge() can * find the pointers without having to know anything about the structure * of the data you are sorting. */ /* * The #ifndef is so that this module can be #included into the program * that calls mSort(), rather than requiring it to be linked in separately. * To avoid a conflicting definition error, #define NextList to be the * name of the pointer to the previous item as it is declared in your * program (for the example given above, user #define NextList Prev). * be sure that the #define and the struct ListItem declaration both * appear before the #include for this module */ #ifndef NextList struct ListItem { struct ListItem *Next; struct ListItem *NextList; }; #endif /* * These are the compare and dispose functions passed to mSort() (see * mSort() for more details), and are assigned to global variables so that * they don't have to be passed to mMerge() every time it is called. */ static int (*mCompare)() = NULL; static void (*mDispose)() = NULL; /* * mMerge() * * combines two sorted linked lists into one sorted linked list, using * the mCompare() function to determine the sorting, and the dispose() * function to remove duplicate values. * * list1 a pointer to the first linked list * list2 a pointer to the second linked list */ struct ListItem * mMerge(list1,list2) struct ListItem *list1, *list2; { static struct ListItem top_item; static struct ListItem *newlist, *temp; static int result; top_item.Next = top_item.NextList = NULL; newlist = &top_item; /* * While there are still items in each list, compare the top items in the * lists. Link the smaller one to the end of the new, combined list, and * pop the item off the top of the old list. If the top items are equal, * then add one of them to the new list, and if there is a dispose function, * get rid of the other one, otherwise add the second one into the list * as well. * * When one of the lists is exauseted, add any remaining items from * the other list onto the end of the result list, and return a pointer * to the final, sorted list. */ while (list1 != NULL && list2 != NULL) { result = (*mCompare)(list1,list2); if (result < 0) { ADD_TO_NEWLIST(list1); list1 = list1->Next; } else if (result > 0) { ADD_TO_NEWLIST(list2); list2 = list2->Next; } else { ADD_TO_NEWLIST(list1); list1 = list1->Next; if (mDispose == NULL) { ADD_TO_NEWLIST(list2); list2 = list2->Next; } else { temp = list2; list2 = list2->Next; temp->Next = temp->NextList = NULL; (*mDispose)(temp); } } } if (list1 != NULL) ADD_TO_NEWLIST(list1); else if (list2 != NULL) ADD_TO_NEWLIST(list2); return(top_item.Next); } /* * mSort() * * sorts a linked list of items of any sort, using a user-provided comparison * routine. Duplicate items will be removed if the dispose routine is * provided. The result list will be a doubly-linked list (pointers go both * forward and backward) that is sorted. mSort() returns a pointer to * the top of the result list. * * cur_item a pointer to the begining of the original, unsorted * list. * compare() a pointer to a function that compares two * ListItems and returns a negative number if * the first item is smaller, zero if they are * equal, and a positive number if the first * item is larger than the second. Compare() * should take two parameters, the pointers * to the ListItems that are to be compared. * dispose() disposes of a duplicate ListItem. Dispose() * should accept one parameter, the pointer to * the ListItem to be removed. Dispose() should * free any memory allocated to the ListItem. * This list item will not appear in the final * linked list. If dispose in NULL, then * duplicate items are retained in the list. */ struct ListItem * mSort(cur_item,compare,dispose) struct ListItem *cur_item; int (*compare)(); void (*dispose)(); { static struct ListItem *first_item, *next_item; /* * Put the compare and dispose routines where mMerge() can find them */ mCompare = compare; mDispose = dispose; first_item = NULL; if (cur_item != NULL) { /* * Put each item in the original list into a separate list. Use the * NextList field to link the individual lists into a list (a linked list * of linked lists). Link the end of the list to the begining so we get * a ring rather than a list. */ first_item = cur_item; do { next_item = cur_item->Next; cur_item->Next = NULL; cur_item->NextList = (next_item != NULL)? next_item : first_item; cur_item = next_item; } while (cur_item != NULL); /* * While there's more than one list left in the ring (i.e., the list * following the current one is not itself), then merge the current list * with the one following it (keep track of the first list after the ones * we're combining so we can link the result of the merge back into * the ring). Finally, if there were more than two lists in the ring * (i.e., if the current list is neither equal to the one preceding it nor * equal to the one after the list with which it was combined), then * link the result list into the ring, otherwise link the result list * to itself (since there were only two lists in the ring, their * merger should leave us with only one). Move down the ring, so we * can merge the next two lists in the ring. */ while ((cur_item = first_item->NextList) != first_item) { next_item = cur_item->NextList->NextList; cur_item = mMerge(cur_item,cur_item->NextList,compare,dispose); if (cur_item == first_item || cur_item == next_item) { cur_item->NextList = cur_item; } else { first_item->NextList = cur_item; cur_item->NextList = next_item; } first_item = cur_item; } /* * When there's only one list left, traverse the list, setting the * reverse pointers so that the list is properly linked both directions. */ first_item->NextList = NULL; while (cur_item->Next != NULL) { cur_item->Next->NextList = cur_item; cur_item = cur_item->Next; } } return(first_item); }