What is Mergesort Algorithm?

The mergesort algorithm is one of the popular and efficient divide and conquer algorithms in computer science, and it is used for sorting a list of items.

While there are a few different mergesort algorithm functions, I will be discussing the top-down method in this article.

How it Works

Mergesort is a sorting algorithm that uses a divide and conquer method to sort a list, by recursively dividing the list into two equal sizes commonly named left and right, and it continues to (apply the same logic) each side of the division until only one item is remaining. After the divisions it will then proceed to sort and merge each of the sides back together again.

Example

In this example I will be showing you how to implement a merge sort algorithm in Swift, we will be using the merge sort to sort a list of random numbers.

MergeSort

We are going to build and separate these machines (functions) away from each so that we can focus directly on what each machine needs to accomplish and build it.

1. Splitting Process Function

This function will be in charge of splitting the items and returning a sorted version of the items.

func mergeSort(for items: [Int]) -> [Int] {
  var leftItems:[Int]
  var rightItems: [Int]
  var result: [Int]

  let length = items.count
}

State Variables

Below are the explanation to the new variable we have just introduced in the function.

• leftItems: We are using it to store the state of each left item of a division
• rightItems: We are also using it to store the state of each right division
• result: Use for storing the result of each sort and merge operation
• length: Used for tracking the size of each side of the division

func mergeSort(for items: [Int]) -> [Int] {
  var leftItems:[Int]
  var rightItems: [Int]
  var result: [Int]

  let length = items.count
  
  if length <= 1 {
      result = items
  }
}

Base Case

if length <= 1 {
    result = items
}

checks if the size of items (the list) is less than or equal to 1 return from the function and quit further splitting. Obviously there would be nothing else to split at this point.

func mergeSort(for items: [Int]) -> [Int] {
  var leftItems:[Int]
  var rightItems: [Int]
  var result: [Int]

  let length = items.count
  
  if length <= 1 {
      result = items
  } else {
      leftItems = Array(items[0..<length / 2])
      rightItems =  Array(items[(length / 2)..<length])
      
      result = merge(for: mergeSort(on: leftItems), and: mergeSort(on: rightItems))
    }
    return result
}

Splitting The Items List

We added an else statement, this will be in charge of splitting the list whenever the (size) length is greater than 1

• leftItems and rightItems: Here we are initializing the leftItems to contain an Array of half size of the items list whenever the function calls itself.
• result: The result, is initialized with result of calling the merge function that is in charge of sorting and merging each division of the items list. Though the merge function, is not yet implemented, and we will do that next.

2. Merge Function

This function accepts and two different lists leftItems and rightItems which are the left and right sides of items list division. The function will now compute and return the result of sorting and merging each list items.

func merge(for leftItems: [Int], and rightItems: [Int]) -> [Int] {
  var result = [Int]()
  var rightPosition = 0
  var leftPosition = 0
}

• result: This will be used to store the result of sorting each item.
• rightPosition and leftPosition: This is used to track the index of each list item starting from 0

func merge(for leftItems: [Int], and rightItems: [Int]) -> [Int] {
  var result = [Int]()
  var rightPosition = 0
  var leftPosition = 0
  
  while (leftPosition < leftItems.count || rightPosition < rightItems.count) {
    // more to come
  }
}

Here we are checking for when either of the list size is greater than either of positions index. It makes sense to only do something whenever we have items with size greater than 1

Sorting And Merging

func merge(for leftItems: [Int], and rightItems: [Int]) -> [Int] {
  var result = [Int]()
  var rightPosition = 0
  var leftPosition = 0
  
  while (leftPosition < leftItems.count || rightPosition < rightItems.count) {
    if (leftPosition < leftItems.count && (rightPosition >= rightItems.count || 
        leftItems[leftPosition] <= rightItems[rightPosition])) {
      
      result.append(leftItems[leftPosition])
      leftPosition += 1
    }
  }
}

Copying From LeftItems

Here we are copying from leftItems list only when the value in the leftItems list is smaller than the value in rightItems list (rightPosition >= rightItems.count || leftItems[leftPosition] <= rightItems[rightPosition]) or when there are no items left in the rightItems. We then add increase the value of lefPosition by 1 after.

func merge(for leftItems: [Int], and rightItems: [Int]) -> [Int] {
  var result = [Int]()
  var rightPosition = 0
  var leftPosition = 0
  
  while (leftPosition < leftItems.count || rightPosition < rightItems.count) {
    if(leftPosition < leftItems.count && (rightPosition >= rightItems.count ||
     leftItems[leftPosition] <= rightItems[rightPosition])){
        
        result.append(leftItems[leftPosition])
        leftPosition += 1
    } else {
        result.append(rightItems[rightPosition])
        rightPosition += 1
    }
  }
  return result
}

Copying From RightItems

Here we are copying from the right items whenever the if statement conditions fails.

Test Function

var myList = [10, 5, 13, 12, 18, 38]
let sortedList = mergeSort(on: myList)

print(sortedList)

Output: [5, 10, 12, 13, 18, 38]