Merge Sort algorithm: Objective -C

Merge Sort algorithm runs in O(n log n) worst case running time. It is one of the easiest algorithms that has a reasonable running time. It’s also fine example of the recursive algorithm.

The fundamental operation in this algorithm is merging two sorted lists. The basic merging algorithm takes two inputs -“leftString” and “rightString”, an output string “result” and three counters, which are initially set to the beggining of their respective arrays. The recursive calls continue dividing the string into pieses until each piece contains only one item; obviously a string of one item is sorted. The algorithms then merges these small pieses into larger sorted pieces until one sorted string results.

• Best, average and worst-case running time: O(n log n)
• Space complexity: O(n)

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.

Although the merge sort is an extremly effisient algorithm with respect to time, it does have one drawback: The merge step requires an auxiliary string. This extra storage and the necessary copying of entries are disadvantages.