Return to MergeSort.m CVS log

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

Sample Programs from NeXSTEP 3.3

/* A fairly fast and extremely stable recursive algorithm.  It divides the 
 * data set into two equal halves, recursively sorts those two halves, and 
 * then merges the results together.  It is very consistent - if makes no 
 * difference if the data is sorted or not.  Merge Sort is always O(nlogn).  
 * As a side note, this sort uses more memory than my other sorts because I 
 * create a new array to hold the sorted and merged array.  I once heard there 
 * was an algorithm to merge the two within the same array, but I couldn't 
 * figure that one out.
 *
 * Author: Julie Zelenski, NeXT Developer Support
 * You may freely copy, distribute and reuse the code in this example.  
 * NeXT disclaims any warranty of any kind, expressed or implied, as to 
 * its fitness for any particular use.
 */
 
 
#import "MergeSort.h"


@implementation MergeSort:GenericSort

- init
{
    [super init];
    sortName = "Merge Sort";
    sortNum = MERGE_SORT;
    return self;
}


- merge:(int)begin to:(int)end middle:(int)middle
{
    int firstHalf, secondHalf, count;
       
    fcalls++;
    firstHalf = count = begin;
    secondHalf = middle + 1;
    while ((firstHalf <= middle) && (secondHalf <= end))
    	tempData[count++] = (![self lessThan:secondHalf :firstHalf])
	   ? data[firstHalf++] : data[secondHalf++]; // merge into temp array
    if (firstHalf <= middle) 
        while (firstHalf <= middle) 
	    tempData[count++] = data[firstHalf++]; // empty out first half
    else
        while (secondHalf <= end) 
	    tempData[count++] = data[secondHalf++]; // or empty out second half
    for (count = begin; count <= end; count++) 
	[self moveValue:tempData[count] to:count];  // move out of temp array
    return self;
}
    

- mergesort:(int)begin to:(int)end
{
    int middle;
    
    fcalls++;
    if (begin != end) {
    	middle = (begin + end) / 2;
	[self mergesort:begin to:middle];		// sort first half
	[self mergesort:(middle+1) to:end];		// sort second half
	[self merge:begin to:end middle:middle];	// merge the two halves
    }
    return self;
}


- sort
{
    [super sort];
    tempData = (int *)calloc(numElements,sizeof(int));	// allocate temp array
    [self mergesort:0 to:(numElements-1)];
    cfree(tempData);				// cfree temporary array
    [self sortDone]; 
    return self;
}
@end

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