Algorithm_ Merge Sort

Merge Sort algorithm: Swift & Objective-C implementations

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

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:

 

Swift Code:

 

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(n2) 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

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:

  • Swift code: link
  • Objective-C code: link

 

Have a nice day 🙂

 

About @marioeguiluz

iOS Freelancer, Entrepreneur and Mobile App Expert

Categories: Algorithm, Development, Objective-C, Sort, Swift

Leave a Reply

Your email address will not be published. Required fields are marked *