home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Examples / AppKit / SortingInAction / MergeSort.m < prev    next >
Encoding:
Text File  |  1990-10-09  |  2.3 KB  |  79 lines
  1.  
  2. /* A fairly fast and extremely stable recursive algorithm.  It divides the 
  3.  * data set into two equal halves, recursively sorts those two halves, and 
  4.  * then merges the results together.  It is very consistent - if makes no 
  5.  * difference if the data is sorted or not.  Merge Sort is always O(nlogn).  
  6.  * As a side note, this sort uses more memory than my other sorts because I 
  7.  * create a new array to hold the sorted and merged array.  I once heard there 
  8.  * was an algorithm to merge the two within the same array, but I couldn't 
  9.  * figure that one out.
  10.  *
  11.  * Author: Julie Zelenski, NeXT Developer Support
  12.  * You may freely copy, distribute and reuse the code in this example.  
  13.  * NeXT disclaims any warranty of any kind, expressed or implied, as to 
  14.  * its fitness for any particular use.
  15.  */
  16.  
  17.  
  18. #import "MergeSort.h"
  19.  
  20.  
  21. @implementation MergeSort:GenericSort
  22.  
  23. - init
  24. {
  25.     [super init];
  26.     sortName = "Merge Sort";
  27.     sortNum = MERGE_SORT;
  28.     return self;
  29. }
  30.  
  31.  
  32. - merge:(int)begin to:(int)end middle:(int)middle
  33. {
  34.     int firstHalf, secondHalf, count;
  35.        
  36.     fcalls++;
  37.     firstHalf = count = begin;
  38.     secondHalf = middle + 1;
  39.     while ((firstHalf <= middle) && (secondHalf <= end))
  40.         tempData[count++] = (![self lessThan:secondHalf :firstHalf])
  41.        ? data[firstHalf++] : data[secondHalf++]; // merge into temp array
  42.     if (firstHalf <= middle) 
  43.         while (firstHalf <= middle) 
  44.         tempData[count++] = data[firstHalf++]; // empty out first half
  45.     else
  46.         while (secondHalf <= end) 
  47.         tempData[count++] = data[secondHalf++]; // or empty out second half
  48.     for (count = begin; count <= end; count++) 
  49.     [self moveValue:tempData[count] to:count];  // move out of temp array
  50.     return self;
  51. }
  52.     
  53.  
  54. - mergesort:(int)begin to:(int)end
  55. {
  56.     int middle;
  57.     
  58.     fcalls++;
  59.     if (begin != end) {
  60.         middle = (begin + end) / 2;
  61.     [self mergesort:begin to:middle];        // sort first half
  62.     [self mergesort:(middle+1) to:end];        // sort second half
  63.     [self merge:begin to:end middle:middle];    // merge the two halves
  64.     }
  65.     return self;
  66. }
  67.  
  68.  
  69. - sort
  70. {
  71.     [super sort];
  72.     tempData = (int *)calloc(numElements,sizeof(int));    // allocate temp array
  73.     [self mergesort:0 to:(numElements-1)];
  74.     cfree(tempData);                // cfree temporary array
  75.     [self sortDone]; 
  76.     return self;
  77. }
  78. @end
  79.