Merge Sort algorithm: Swift & Objective-C implementations

11 May, 2015 No comments Article

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).

How Merge Sort algorithm works?

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.

Objective-C code:

////////////////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));
}

////////////////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));

}

Swift Code:

//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
}

//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

}

Efficiency & facts:

Best, average and worst-case running time: O(n log n)
Space complexity: O(n)
It is a divide and conquer algorithm
Better running time than insertion sort, bubble sort, and the rest of O(n²) algorithms.
However, when the input size is not too big, insertion sort can be more efficient. There are some implementations that use insertion sort until some threshold is reached, and then, they use merge sort, combining both of them for the best results.

Algorithm chart from bigocheatsheet.com:

Algorithm sort comparison (bigocheatsheet.com)

Any improvements?

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: