Skip to content

Instantly share code, notes, and snippets.

@antonio081014
Last active December 2, 2015 19:42
Show Gist options
  • Save antonio081014/ccb7bddc017407976afd to your computer and use it in GitHub Desktop.
Save antonio081014/ccb7bddc017407976afd to your computer and use it in GitHub Desktop.
This is the Merge-Sort implementation written in Objective-C.
/**
* Divide and Conque Algorithm.
*/
- (NSArray *)mergesort:(NSArray *)array
/**
* The following two implementation introduced a few Objective-C knowledge hints I used to miss.
* 1st, Objective-C is just like C language, it pass-by-value instead of pass-by-reference,
* even pass a pointer address, it's still a value. You can't assign a new address to it.
* 2nd, [[NSMutableArray alloc] initWithCapacity:count]; would create an empty mutable array, which has nothing in it. You could either addObject: to it,
* or set the first unsigned index to an object.
* E.g, If you just send the message "initWithCapacity:", it's an empty mutable array, you could addObject: which add the object to the array,
* and its index is 0. Or, you could just assign the 0th index with the object. You can't assign the object to other index at this moment.
* Like, you could not assign 1st index with object, otherwise, a runtime error will popup when you run it.
*/
- (NSArray *)mergesort:(NSArray *)array
{
NSInteger count = array.count;
NSMutableArray *helper = [[NSMutableArray alloc] initWithCapacity:count];
NSMutableArray *ret = [array mutableCopy];
[self mergesort:ret withHelperArray:helper from:0 to:count-1];
return ret;
}
- (void)mergesort:(NSMutableArray *)array withHelperArray:(NSMutableArray *)helper from:(NSInteger)low to:(NSInteger)high
{
if (low >= high) return;
NSInteger mid = (low + high) / 2;
[self mergesort:array withHelperArray:helper from:low to:mid];
[self mergesort:array withHelperArray:helper from:mid+1 to:high];
[self merge:array withHelperArray:helper from:low mid:mid to:high];
}
- (void)merge:(NSMutableArray *)array withHelperArray:(NSMutableArray *)helper from:(NSInteger)low mid:(NSInteger)mid to:(NSInteger)high
{
for(NSInteger i = low; i<= high; i++) {
helper[i] = array[i];
}
NSInteger left1 = low;
NSInteger left2 = mid + 1;
NSInteger index = low;
while(left1 <= mid || left2 <= high) {
if(left1 <= mid && left2 <= high) {
if ([helper[left1] integerValue] <= [helper[left2] integerValue]) {
array[index] = helper[left1];
left1++;
} else {
array[index] = helper[left2];
left2++;
}
index++;
} else if (left1 <= mid) {
array[index] = helper[left1];
left1++;
index++;
} else if (left2 <= high) {
array[index] = helper[left2];
left2++;
index++;
}
}
}
- (NSArray *)mergesort:(NSArray *)array
{
NSMutableArray *ret = [array mutableCopy];
[self mergesort:ret from:0 to:array.count-1];
return ret;
}
- (void)mergesort:(NSMutableArray *)array from:(NSInteger)low to:(NSInteger)high
{
if (low >= high) return;
NSInteger mid = (low + high) / 2;
[self mergesort:array from:low to:mid];
[self mergesort:array from:mid+1 to:high];
[self merge:array from:low mid:mid to:high];
}
- (void)merge:(NSMutableArray *)array from:(NSInteger)low mid:(NSInteger)mid to:(NSInteger)high
{
NSMutableArray *helper = [[NSMutableArray alloc] initWithCapacity:array.count];
for(NSInteger i = 0; i< array.count; i++) {
[helper addObject:array[i]];
}
NSInteger left1 = low;
NSInteger left2 = mid + 1;
NSInteger index = low;
while(left1 <= mid || left2 <= high) {
if(left1 <= mid && left2 <= high) {
if ([helper[left1] integerValue] <= [helper[left2] integerValue]) {
array[index] = helper[left1];
left1++;
} else {
array[index] = helper[left2];
left2++;
}
index++;
} else if (left1 <= mid) {
array[index] = helper[left1];
left1++;
index++;
} else if (left2 <= high) {
array[index] = helper[left2];
left2++;
index++;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment