Merge Sort algorithm is one of the most common algorithms in books. It is the most used example to explain the divide and conquer technique. Furthermore, it is one of the easiest algorithms that has a reasonable running time for a big input => O(n log n).
This graph shows the process:
Merge sort algorithm (source: Wikipedia)
If you want to know how Merge Sort algorithm works in detail, I recommend you to read this article: Wikipedia – Merge Sort
Let’s see how we can implement this algorithm with Objective-C and Swift.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
////////////////MERGE SORT//////////////// NSArray* mergeArrays(NSArray* A, NSArray* B) { NSMutableArray *orderedArray = [NSMutableArray new]; long indexLeft = 0; long indexRight = 0; while (indexLeft < [A count] && indexRight < [B count]) { if ([A[indexLeft] intValue] < [B[indexRight]intValue]) { [orderedArray addObject:A[indexLeft++]]; }else if ([A[indexLeft] intValue] > [B[indexRight]intValue]){ [orderedArray addObject:B[indexRight++]]; }else { //equal values [orderedArray addObject:A[indexLeft++]]; [orderedArray addObject:B[indexRight++]]; } } //If one array has more positions than the other (odd lenght of the inital array) NSRange rangeRestLeft = NSMakeRange(indexLeft, A.count - indexLeft); NSRange rangeRestRight = NSMakeRange(indexRight, B.count - indexRight); NSArray *arrayTotalRight = [B subarrayWithRange:rangeRestRight]; NSArray *arrayTotalLeft = [A subarrayWithRange:rangeRestLeft]; arrayTotalLeft = [orderedArray arrayByAddingObjectsFromArray:arrayTotalLeft]; NSArray *orderedArrayCompleted = [arrayTotalLeft arrayByAddingObjectsFromArray:arrayTotalRight]; return orderedArrayCompleted; } NSArray* mergeSort(NSArray* randomArray){ if ([randomArray count] < 2) { return randomArray; } int middlePivot = (int)[randomArray count]/2; NSRange rangeLeft = NSMakeRange(0, middlePivot); NSRange rangeRight = NSMakeRange(middlePivot, randomArray.count-middlePivot); NSArray *leftArray = [randomArray subarrayWithRange:rangeLeft]; NSArray *rightArray = [randomArray subarrayWithRange:rangeRight]; return mergeArrays(mergeSort(leftArray),mergeSort(rightArray)); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
//Merge Sort func mergeSort<T:Comparable>(_ unsortedArray:Array<T>)->Array<T>{ var unsortedArray = unsortedArray if unsortedArray.count < 2 { return unsortedArray } let pivot:Int = unsortedArray.count/2 let leftArray:Array<T> = Array(unsortedArray[0..<pivot]) let rightArray:Array<T> = Array(unsortedArray[pivot..<unsortedArray.count]) return mergeArrays(mergeSort(leftArray), B: mergeSort(rightArray)) } func mergeArrays<T:Comparable>(_ A:Array<T>,B:Array<T>)->Array<T>{ let leftIndex = 0 let rightIndex = 0 var orderedArray:Array<T> = [] while leftIndex<A.count && rightIndex<B.count { if A[leftIndex] < B[rightIndex] { orderedArray.append(A[leftIndex+1]) } else if A[leftIndex] > B[rightIndex] { orderedArray.append(B[rightIndex+1]) } else { orderedArray.append(A[leftIndex+1]) orderedArray.append(B[rightIndex+1]) } } orderedArray = orderedArray + Array(A[leftIndex..<A.count]) orderedArray = orderedArray + Array(B[rightIndex..<B.count]) return orderedArray } |
Algorithm chart from bigocheatsheet.com:
Hey reader! This post only tries to give some basic idea and an easy implementation of the algorithm. If you have a better approach, some fix or some clarification to make, you are welcome!!! We can improve this together
You can make comments on the code via Gist:
Have a nice day 🙂
Categories: Algorithm, Development, Objective-C, Sort, Swift
Leave a Reply