/********************************************************************** * mergesort.cc * Tom Kelliher * * Demonstrates the mergesort algorithm **********************************************************************/ #include #include #include #include const int DATA_SIZE = 20; // Number of ints to sort. // Prototypes. void mergesort(int *, int); void merge(int *, int); void move(int *, int *, int); /********************************************************************** * main **********************************************************************/ int main() { int data[DATA_SIZE]; // Storage for int to be sorted. int *intptr, // "Index" pointer. // Seed the random number generator. srand((unsigned) time((time_t *) NULL)); cout << "\nUnsorted list:\n\n"; // Get random numbers for the unsorted data. for (intptr = data; intptr < data + DATA_SIZE; intptr++) cout << (*intptr = rand()) << endl; mergesort(data, DATA_SIZE); cout << "\nSorted list:\n\n"; for (intptr = data; intptr < data + DATA_SIZE; intptr++) cout << *intptr << endl; return (0); } /********************************************************************** * mergesort * * data is the address of the first element to be sorted. * len is the number of elements to sort. **********************************************************************/ void mergesort(int *data, int len) { int half = len / 2; if (len < 2) return; mergesort(data, half); // Sort first half of data. mergesort(data + half, len - half); // Sort second half of data. // Merge two sorted halves into a sorted whole. merge(data, len); } /********************************************************************** * merge * * data is the address of the first element to be merged. * len is the number of elements in BOTH halves to be merged. **********************************************************************/ void merge(int *data, int len) { int half = len / 2; int *p1 = data; // Pointer to elements in first half. int *p2 = data + half; // Pointer to elements in second half. int *ary, *ap; // Pointers for temporary array. // The merged whole is temporarily stored here. assert ((ap = ary = new int[len]) != NULL); // While neither half is exhausted, look at smallest element in // each half, moving the smaller into the temporary array. while (p1 < data + half && p2 < data + len) if (*p1 < *p2) *ap++ = *p1++; else *ap++ = *p2++; // Still a few elements left in first half, move them over to the // temporary array. if (p1 < data + half) move(ap, p1, data + half - p1); else // Elements left in the second half. Move them. move(ap, p2, data + len - p2); // Move elements from the temporary array back to the original array. move(data, ary, len); delete [] ary; // Discard the temporary array. } /********************************************************************** * move * * Move len ints from source to target. **********************************************************************/ void move(int *target, int *source, int len) { int i; for (i = 0; i < len; i++) *target++ = *source++; }