Mergesort

excerpt: This covers the mergesort algorithm and implementation that illustrates divide and conquer strategy. tags: two-pointers two-way-merge divide-and-conquer

Mergesort uses divide and conquer strategy. The array is split into two halves of equal size. The two halves are sorted by recursive calls. During the return phase of the recursive calls, the two sorted halves are merged into a combined sorted list.

Recursive Implementation

The parameter to the mergesort method consists of the input array to be sorted, start and stop indices to sort and an output array that is used to merge the sorted halves.

The base case checks whether the array has one or fewer items. If if does, there is nothing to sort, so it returns. If the subarray contains at least two items, find the middle index of the subarray and make the recursive calls to sort the two halves.

During the return phase of the recursive calls, the two sorted halves are merged into one array. The merging is performed by looping through the halves copying the smaller item from whichever half holds it into the output array. When one half is empty, the remaining items is copied from the other half.

Finally, the merged items are copied from the output array back into the original input array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

def mergesort(input, output, start, stop)
  # If the array contains only one item, there is nothing to sort
  if start == stop
    return
  end
  
  # Split the array into left and right halves
  mid = (start + stop)/2
  
  # Recursive calls to sort the two halves
  mergesort(input, output, start, mid)
  mergesort(input, output, mid+1, stop)
  
  # Merge the two sorted halves
  left_index = start
  right_index = mid + 1
  output_index = left_index
  
  while (left_index <= mid) && (right_index <= stop)
    if input[left_index] <= input[right_index]
      output[output_index] = input[left_index]
      left_index = left_index + 1
    else
      output[output_index] = input[right_index]
      right_index = right_index + 1
    end
    
    output_index = output_index + 1
  end
  
  # Copy any left over elements
  for i in (left_index..mid)
    output[output_index] = input[i]
    output_index = output_index + 1
  end
  
  for i in (right_index..stop)
    output[output_index] = input[i]
    output_index += 1
  end
  
  # Copy the values back into the original input array
  for i in (start..stop)
    input[i] = result[i]
  end
end

The mergesort algorithm divides the items into equal havles at every step. The runtime is O(N log N).

Alternative Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

def merge(left, right)
  i = 0
  j = 0
  
  result = []
  
  while i < left.size && j < right.size
    if left[i] <= right[j]
      result << left[i]
      i += 1
    else
      result << right[j]
      j += 1
    end
  end
  
  while i < left.size
    result << left[i]
    i += 1
  end
  
  while j < right.size
    result << right[j]  
    j += 1
  end
  
  return result
end

def mergesort(array, low, high)  
  if low >= high
    return array[low..high]
  end
  
  # Avoid overflow error
  mid = low + (high - low)/2
  # Right shift to divide by 2
  # mid = (low + high) >> 1
  
  left = mergesort(array, low, mid)
  right = mergesort(array, mid+1, high)
    
  merge(left, right)
end

array = [12, 8, 4, 10, 15, 3, 1, 5]

p mergesort(array, 0, array.size-1)

The mergesort method returns an array, this is saved in the left and right variables which is used by the merge method to sort the arrays.

The merge function must preserve the order. This is important for the stability property of the sorting algorithm. Iterate through the elements of the two sorted list. Depending on how they compare, decide which element comes first in the merged list. Mergesort typically uses an extra list. More space can hurt performance for big lists.

Merge Drill

Write a function that merges two sorted lists into a new sorted list. [1,4,6],[2,3,5] → [1,2,3,4,5,6]. You can do this quicker than concatenating them followed by a sort.

Building Blocks

  • Two Pointers
  • Two Way Merge

Language Agnostic Coding Drills

Let’s break down the merge sort algorithm into several smaller learning units:

  1. Understanding of Arrays/List: Know how to declare, access, and modify an array or list.

  2. Concept of Recursion: The basic concept of recursion, how it works, and its use cases.

  3. Divide and Conquer Strategy: Understand the strategy of divide and conquer in which we divide the problem into smaller subproblems until the problem becomes simple enough to be solved directly.

  4. The Idea of Sorting: Understanding of the idea of sorting and various sorting algorithms, specifically the idea of a comparison sort.

  5. Merge Sort Algorithm: Understand the mechanism of merge sort, how it divides the array into two halves, sorts them separately, and merges them.

  6. Implementation of the Merge Function: This function is used to merge two halves. The merged subarray should also be sorted.

  7. Recursive Definition of Merge Sort: Understand how to use recursion to sort the left half and the right half of the array independently before merging them.

  8. Combining it All: Combine the divide, conquer (recursive sorting), and merge processes to write the complete merge sort algorithm.

  9. Analysis of Merge Sort: Understand the time complexity (O(n log n) in all cases) and space complexity (O(n)) of merge sort.

  10. Adaptations and Optimizations: Learn about common adaptations and optimizations of merge sort (e.g., switching to a different sort for small subarrays, avoiding the copy to the auxiliary array, etc.).

Starting from understanding the basics of arrays and recursion, we progress towards more specific concepts like sorting, merge sort algorithm, and finally its analysis and optimization.

Let’s break down the more complex units further:

  1. Concept of Recursion:

    • Understanding Function Calls: Understand how function calls work in the language of your choice.
    • Base Case and Recursive Case: Understand the distinction between a base case (which ends the recursion) and a recursive case (which includes a call to the same function).
    • Stack Behavior in Recursion: Understand how the call stack works with recursive function calls.

  2. Divide and Conquer Strategy:

    • Problem Decomposition: Learn how to break a problem down into smaller subproblems.
    • Recursive Solution: Understand how to apply recursion to solve each subproblem.
    • Combining Solutions: Understand how to combine the solutions of the subproblems to solve the main problem.

  3. The Idea of Sorting:

    • Order and Comparisons: Understand what it means for elements to be in order and how to compare elements.
    • Sorting Algorithms: Learn about different types of sorting algorithms and their characteristics (e.g., bubble sort, selection sort, insertion sort).

  4. Merge Sort Algorithm:

    • Conceptual Understanding: Understand the concept of the merge sort algorithm, including dividing, sorting, and merging.
    • Divide Process: Understand how the algorithm divides the original array into smaller subarrays.
    • Merge Process: Understand how the sorted subarrays are merged back together.

  5. Implementation of the Merge Function:

    • Merging Two Sorted Arrays: Understand how to merge two sorted arrays into a single sorted array.
    • Working With Indices: Be comfortable with manipulating array indices to navigate through the arrays.

  6. Recursive Definition of Merge Sort:

    • Recursive Sorting: Understand how the merge sort algorithm uses recursion to sort subarrays.
    • Array Partitioning: Be able to partition an array into two halves to be sorted separately.

  7. Analysis of Merge Sort:

    • Big O Notation: Understand Big O notation and how to derive the time complexity of an algorithm.
    • Time Complexity Analysis: Be able to analyze the time complexity of the merge sort algorithm.
    • Space Complexity Analysis: Understand the concept of space complexity and be able to analyze the space complexity of the merge sort algorithm.

  8. Adaptations and Optimizations:

    • Algorithm Variants: Learn about common variations of merge sort and when they might be useful.
    • Trade-offs: Understand the trade-offs involved in choosing one variant or optimization over another.

These subtopics break down the original topics into more manageable units of learning.

Solution for Coding Drills in Python

Let’s create coding drills based on the learning units. Here they are, from easier to more difficult:

  1. Understanding Function Calls:

    • Drill: Create a function that takes an integer as a parameter and prints it.
    1
2
3

    def print_num(num):
    print(num)
print_num(5)

  2. Base Case and Recursive Case:

    • Drill: Write a recursive function to compute the factorial of an integer.
    1
2
3
4
5
6

    def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
print(factorial(5))

  3. Problem Decomposition:

    • Drill: Write a function that takes a list of numbers and returns a new list that contains only the numbers that are divisible by a given number.
    1
2
3

    def filter_divisible_by(numbers, divisor):
    return [num for num in numbers if num % divisor == 0]
print(filter_divisible_by([1, 2, 3, 4, 5, 6], 2))

  4. Order and Comparisons:

    • Drill: Write a function that takes a list of numbers and checks whether the list is sorted in ascending order.
    1
2
3

    def is_sorted(numbers):
    return numbers == sorted(numbers)
print(is_sorted([1, 2, 3, 4, 5]))

  5. Merging Two Sorted Arrays:

    • Drill: Write a function that takes two sorted lists and returns a new sorted list that combines the elements of the input lists.
    1
2
3

    def merge_sorted_lists(list1, list2):
    return sorted(list1 + list2)
print(merge_sorted_lists([1, 3, 5], [2, 4, 6]))

  6. Recursive Sorting:

    • Drill: Implement a basic recursive sorting algorithm, such as quicksort.
    1
2
3
4
5
6
7
8
9

    def quicksort(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    left = [x for x in array if x < pivot]
    middle = [x for x in array if x == pivot]
    right = [x for x in array if x > pivot]
    return quicksort(left) + middle + quicksort(right)
print(quicksort([3,6,8,10,1,2,1]))

  7. Big O Notation and Time Complexity Analysis:

    • Drill: Write a function that takes a list of numbers and a number n, and returns a new list containing each number of the input list repeated n times. Analyze its time complexity.
    1
2
3
4

    def repeat_numbers(numbers, n):
    return [num for num in numbers for _ in range(n)]
print(repeat_numbers([1, 2, 3], 2))
# Time Complexity: O(n^2)

  8. Full Merge Sort Algorithm:

    • Drill: Implement the full merge sort algorithm.
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

    def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    left_list = merge_sort(lst[:mid])
    right_list = merge_sort(lst[mid:])

    return merge(left_list, right_list)

def merge(left, right):
    sorted_list = []
    while left and right:
        if left[0] <= right[0]:
            sorted_list.append(left.pop(0))
        else:
            sorted_list.append(right.pop(0))

    while left:
        sorted_list.append(left.pop(0))
    while right:
        sorted_list.append(right.pop(0))

    return sorted_list

print(merge_sort([64, 34, 25, 12, 22, 11, 90]))

These drills should help understand the core concepts behind the Merge Sort algorithm and improve coding skills along the way.