Sorting Algorithm in Swift: Merge Sort (Part — 3)

We are now heading towards the fast sorting algorithms and which are very useful in sorting large arrays with best time and space complexities.

Before we move forward, If you want to start with basic sorting algorithms then please goto part — 1 and part-2 of algorithms series.

One of the algorithm which is very popular and Widely used by many Standard library i.e. Merge Sort. Which is based on Divide and conquer approach!!

Merge Sort (Fast sorting algorithm)

Let’s start quickly on how does Merge sort work and what is quicker way to implement in swift.

Steps:

1. Put the numbers in unsorted array.
2. Create a function which take the unsorted array.
3. Divide unsorted array into 2 arrays. Now you have 2 unsorted arrays.
4. Keep splitting the array until their count goes down to 1 (Use recursion todo this)
5. Then conquer the array together by pairing then sequentially.
6. Put the content in sorted order on each merge. Its easy because each individual array is already sorted.

Example:

Image picked from here

Code snippet:

// MARK: Merge Sort
/// I have done Merge sort in Ascending order
/// If we want to change sorting order of string then change comparator operator < to >
///
func mergeSort<T: Comparable>(list:[T]) -> [T] {
 guard list.count > 1 else {
  return list
  }
 let leftList = Array(list[0..<list.count/2])
 let rightList = Array(list[list.count/2..<list.count])
 return merge(left: mergeSort(list:leftList), right:    mergeSort(list:rightList))
}
func merge<T: Comparable>(left:[T], right:[T]) -> [T] {
  var mergedList = [T]()
  var left = left
  var right = right
  while left.count > 0 && right.count > 0 {
    if left.first! < right.first! {
       mergedList.append(left.removeFirst())
    } else {
      mergedList.append(right.removeFirst())
    }
 }
 return mergedList + left + right
}

Usage:

var intArrayToBeSorted = [1,1,45,23,11,76,25,98,34,56]
print(mergeSort(list: intArrayToBeSorted))
var doubleArrayToBeSorted = [1,1.5,45.1,23.22,11,76,25,98,34,56]
print(mergeSort(list: doubleArrayToBeSorted))
// Empty space is present in the end of sorted string
var stringToBeSorted = "Sort Bubbles"
var stringToArray = Array(stringToBeSorted)
print(mergeSort(list: stringToArray))

Complexities:

Best Case: O(n log n)

Worst Case: O(n log n)

Average Case: O(n log n)

When to use:

• Can be used for external sorting.
• Highly parallelizable
• Stable sort

Cons:

• It’s marginally slow to Quick sort as in Merge Sort there is temporary “working” array equal in size to the array being sorted.
• Not best in space management.

Merge Sort looks scary but its pretty straight forward.

Image used from here

Happy Coding!!