home *** CD-ROM | disk | FTP | other *** search
/ C by Discovery (4th Edition) / C_By_Discovery_4th_Edition.tar / C_By_Discovery_4th_Edition / _DISK_ / ch6 / mergsort.c < prev    next >
C/C++ Source or Header  |  2005-06-16  |  2KB  |  65 lines
  1. /*                 mergsort.c
  2.  */
  3.  
  4. /* Include Files */
  5. #include "mergsort.h"                                /* Note 1 */
  6.  
  7. /*******************************merge_sort()********************/
  8.  
  9.                                                      /* Note 2 */
  10. void merge_sort( int to_sort[], int first, int last )
  11. {
  12.      if ( first < last ) {                           /* Note 3 */
  13.                                                      /* Note 4 */
  14.           merge_sort( to_sort, first, (first+last)/2 );
  15.                                                      /* Note 5 */
  16.           merge_sort( to_sort, (first+last)/2 + 1, last );
  17.                                                      /* Note 6 */
  18.           merge( to_sort, first, (first+last)/2, (first+last)/2 + 1, last );
  19.      }
  20. }
  21.  
  22. /*******************************merge()*************************/
  23.  
  24. void merge( int lists[], int first1, int last1, int first2, int last2 )
  25. {
  26.      int temp[MAX_ARRAY];
  27.      int index, index1, index2;
  28.      int num;
  29.  
  30.      index = 0;
  31.      index1 = first1;
  32.      index2 = first2;
  33.      num = last1 - first1 + last2 - first2 + 2;
  34.  
  35.      /* while there are still elements in both lists,
  36.       * put the smallest element in the temporary array.
  37.       */
  38.      while (( index1 <= last1 ) && ( index2 <= last2 )) {
  39.  
  40.           if ( lists[index1] < lists[index2] )
  41.                temp[index++] = lists[index1++];
  42.           else
  43.                temp[index++] = lists[index2++];
  44.      }
  45.  
  46.      /* after one list is empty, fill the temporary array
  47.       * with the remaining elements in the other list
  48.       */
  49.      if ( index1 > last1 )                 /* first list is empty */
  50.           move( lists, index2, last2, temp, index );
  51.      else                                 /* second list is empty */
  52.            move( lists, index1, last1, temp, index );
  53.  
  54.      /* copy the list to original array */
  55.      move( temp, 0, num-1, lists, first1 );
  56. }
  57.  
  58. /*******************************move()**************************/
  59.  
  60. void move( int list1[], int first1, int last1, int list2[], int first2 )
  61. {
  62.      while ( first1 <= last1 )
  63.           list2[ first2++ ] = list1[ first1++ ];
  64. }
  65.