December 17, 2017 Andrey

Merge Sort in Objective-C

An implementation of the merge sort. Coded according to a Top-Down C example from Wikipedia. https://en.wikipedia.org/wiki/Merge_sort

// Array A[] has the items to sort; array B[] is a work array.
- (void)topDownMergeSort:(NSMutableArray*)A array:(NSMutableArray*) B int:(int) n{
    [self copyArray:A begin:0 end:n array:B];      // duplicate array A[] into B[]
    [self topDownSplitMerge:B begin:0 end:n array:A];// sort data from B[] into A[]
}

- (void)topDownSplitMerge:(NSMutableArray*)B begin:(int)iBegin end:(int)iEnd array:(NSMutableArray*)A {
    if(iEnd - iBegin < 2)                       // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    int iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    [self topDownSplitMerge:A begin:iBegin end:iMiddle array:B];// sort the left  run
    [self topDownSplitMerge:A begin:iMiddle end:iEnd array:B];// sort the right run
  
    // merge the resulting runs from array B[] into A[]
    [self topDownMerge:B begin:iBegin middle:iMiddle end:iEnd array:A];
}

- (void)topDownMerge:(NSMutableArray*)A begin:(int)iBegin middle:(int)iMiddle end:(int)iEnd array:(NSMutableArray*)B {
    int i = iBegin;
    int j = iMiddle;
    
    // While there are elements in the left or right runs...
    for (int k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

- (void)copyArray:(NSMutableArray*)A begin:(int)iBegin end:(int)iEnd array:(NSMutableArray*)B {
    for (int i = iBegin; i<iEnd; i++){
        [B setObject:[A objectAtIndex:i] atIndexedSubscript:i];
    }
}

Algorithm can be tested with the following input:

 NSMutableArray* a =[[NSMutableArray alloc] initWithObjects:@10,@1, @20, @15, @30, nil];
    NSMutableArray* b = [[NSMutableArray alloc] init];
    
    [self topDownMergeSort:a array:b int:a.count];
    NSLog(@"%@", a);

Result that is printed:
2017-12-17 10:57:53.010807-0500 testCode[9627:2980041] (
1,
10,
15,
20,
30
)