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
)