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     ! 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.