Merge Sorting in Objective C

Question

I am trying to implement merge sort in objective -C.

This is a similar question asked in the following link , did not find it answered so creating a new question.

Merge sort in Objective-C

This is what I have tried ,

-(NSArray *)mergeSort:(NSArray *)unsortedArray {

    if ([unsortedArray count] < 2)
        return unsortedArray;

    long mid = [unsortedArray count] / 2;
    NSRange left = NSMakeRange(0, mid);
    NSRange right = NSMakeRange(mid, [unsortedArray count] - mid);

    NSArray *rightArray = [unsortedArray subarrayWithRange:right];
    NSArray *leftArray = [unsortedArray subarrayWithRange:left];

    NSArray *resultArray = [self merge:leftArray andRight:rightArray];
    return resultArray;
}

-(NSArray *)merge:(NSArray *)leftArray andRight:(NSArray *)rightArray {

    NSMutableArray *result = [NSMutableArray array];
    int right = 0;
    int left = 0;

    while (left < [leftArray count] && right < [rightArray count]) {

        NSComparisonResult comparisonResult = [leftArray[left] compare:rightArray[right]];

        if (comparisonResult != NSOrderedDescending) {
            [result addObject:[leftArray objectAtIndex:left++]];
        } else {
            [result addObject:[rightArray objectAtIndex:right++]];
        }

        /*if ([[leftArray objectAtIndex:left] intValue] < [[rightArray objectAtIndex:right] intValue]) {
            [result addObject:[leftArray objectAtIndex:left++]];
            //left++;
        } else {
            [result addObject:[rightArray objectAtIndex:right++]];
            //right++;
        }*/
    }

    NSRange leftRange = NSMakeRange(left, [leftArray count] - left);
    NSRange rightRange = NSMakeRange(right, [rightArray count] - right);
    NSArray * newRight = [rightArray subarrayWithRange:rightRange];
    NSArray * newLeft = [leftArray subarrayWithRange:leftRange];
    newLeft = [result arrayByAddingObjectsFromArray:newLeft];

    return [newLeft arrayByAddingObjectsFromArray:newRight];
}

Kindly let me know if anyone has any other approaches for merge sort.

Answer 1

I dont understand why do you people want the long way.. Even though there are already easy way of doing this...

I made one myself hope this will help you..

- (NSArray *)arrayMergeSort:(NSArray *)targetArray
{
    if (targetArray.count < 2)
        return targetArray;

    long midIndex = targetArray.count/2;

    NSArray *arrayLeft = [targetArray subarrayWithRange:NSMakeRange(0, midIndex)];

    NSArray *arrayRight= [targetArray subarrayWithRange:NSMakeRange(midIndex, targetArray.count - midIndex)];

    return [self arrayMerge: [self arrayMergeSort:arrayLeft] : [self arrayMergeSort:arrayRight]];
}

For arrange merge:

- (NSArray *)arrayMerge:(NSArray *)arrayLeft :(NSArray *)arrayRight 
{
    NSMutableArray *resultArray = [[NSMutableArray alloc] init];

    int i = 0, j = 0;

    while (i < arrayLeft.count && j < arrayRight.count)
        [resultArray addObject:([arrayLeft[i] intValue] < [arrayRight[j] intValue]) ? arrayLeft[i++] : arrayRight[j++]];

    while (i < arrayLeft.count)
        [resultArray addObject:arrayLeft[i++]];

    while (j < arrayRight.count)
        [resultArray addObject:arrayRight[j++]];

    return resultArray;
}

And using it like:

//Sample array
NSArray *activeArray = @[@101,@201,@301,@121,@11,@123,@21,@14,@32,@76,@89,@987,@65];

NSLog(@"arrayMergeSort %@",[self arrayMergeSort:activeArray]);

Output would be:

And also this bubble sort if you needed this:

- (NSArray *)arrayBubbleSort:(NSArray *)targetArray
{
    NSMutableArray *resultArray = [targetArray mutableCopy];

    for (int k = 0; k < resultArray.count; k++)
    {
        for (int l = 0; l < resultArray.count; l++)
        {
            if ([resultArray[k] intValue] < [resultArray[l] intValue])
            {
                [resultArray exchangeObjectAtIndex:k withObjectAtIndex:l];
            }
        }
    }

    return resultArray;
}

Hope i've helped you.. Cheers..

Answer 2

You've made a simple mistake. Merge sort works my splitting the array, sorting to the two halves, then merging the results.

Your mergeSort: method does the split, doesn't sort the two halves, and then calls merge: to merge the two (unfortunately unsorted) halves.

Before calling merge: you need to make recursive calls to mergeSort: to sort the two halves - this is the simple step you missed out.

I'm guessing this in a learning exercise, so no code, but you're almost there (fix it and it does work).

BTW Once you've fixed it you might want to think about why you don't need to create new arrays for the split part (but its far easier to create a new array for the merges).

HTH