Skip to content

Instantly share code, notes, and snippets.

@henrytkirk
Created December 15, 2014 02:07
Show Gist options
  • Save henrytkirk/764f4bbcff8d35457ff5 to your computer and use it in GitHub Desktop.
Save henrytkirk/764f4bbcff8d35457ff5 to your computer and use it in GitHub Desktop.
MergeSort with Objective-C
- (NSArray *)mergeSort:(NSArray *)array {
if (array.count == 1) {
return array;
}
// Split array in two
NSInteger firstHalfCount = array.count/2;
NSInteger secondHalfCount = array.count - firstHalfCount;
NSArray *arrayOne = [array subarrayWithRange:NSMakeRange(0, firstHalfCount)];
NSArray *arrayTwo = [array subarrayWithRange:NSMakeRange(firstHalfCount, secondHalfCount)];
// Recursively split until we have one element in each
NSArray *sortedFirst = [self mergeSort:arrayOne];
NSArray *sortedSecond = [self mergeSort:arrayTwo];
// Merge together
NSArray *merged = [self mergeFirstArray:sortedFirst withSecondArray:sortedSecond];
// Return merged
return merged;
}
- (NSArray *)mergeFirstArray:(NSArray *)firstArray withSecondArray:(NSArray *)secondArray {
NSMutableArray *mergedArray = [NSMutableArray array];
NSInteger firstIndex = 0;
NSInteger secondIndex = 0;
// Merge elements
while (firstIndex < firstArray.count && secondIndex < secondArray.count) {
// Merge
NSNumber *firstItem = firstArray[firstIndex];
NSNumber *secondItem = secondArray[secondIndex];
if (firstItem.integerValue < secondItem.integerValue) {
[mergedArray addObject:firstItem];
firstIndex++;
} else {
[mergedArray addObject:secondItem];
secondIndex++;
}
}
// Add any elements left over (they will already be sorted)
while (firstIndex < firstArray.count) {
[mergedArray addObject:firstArray[firstIndex]];
firstIndex++;
}
// Add any elements left over (they will already be sorted)
while (secondIndex < secondArray.count) {
[mergedArray addObject:secondArray[secondIndex]];
secondIndex++;
}
return mergedArray;
}
@henrytkirk
Copy link
Author

Assumes an array of NSNumber objects.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment