Return to MergeSort.m CVS log

Up to [NeXTSTEP 3.3 examples] / Examples / AppKit / SortingInAction

Annotation of Examples/AppKit/SortingInAction/MergeSort.m, revision 1.1.1.1

1.1       root        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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.