Merge Sort

Mergesort is a type of sorting algorithm that is widely used in computer science. It is a divide-and-conquer algorithm that splits a large problem into subproblems, solves each subproblem individually, and then merges the solutions together to obtain the final result. Mergesort is one of the most popular sorting algorithms due to its simplicity and efficiency. In this article, we will discuss the time and space complexity of Mergesort, as well as provide some examples of Python code for implementing the algorithm. We will also provide five coding exercises with solutions to test the reader’s understanding of what was covered in the article.

What is Mergesort?

Mergesort is an efficient, general-purpose sorting algorithm that uses the divide-and-conquer paradigm. In divide-and-conquer algorithms, a large problem is divided into smaller subproblems that can be solved independently. This type of algorithm has the advantage of reducing the amount of work required to solve a problem, since each subproblem can be solved in parallel.

The basic idea of Mergesort is to divide an array of elements into two equal-sized subarrays, and then recursively sort each subarray. The subarrays are then merged back together in sorted order. The process is repeated until the entire array is sorted.

How does Mergesort Work?

Mergesort is an efficient, divide and conquer, comparison-based sorting algorithm. It is one of the most popular sorting algorithms and is commonly used due to its efficiency, stability, and ease of implementation. Mergesort works by first dividing the array into two halves, then recursively sorting each half, and finally merging the two sorted halves together.

The first step is to divide the array into two halves. This is done by taking the midpoint of the array, which is the element at the middle index. Then the elements to the left of the midpoint are placed in one array and the elements to the right of the midpoint are placed in another array. This process is then repeated until each array has only one element.

The next step is to recursively sort each half. This is done by calling the Mergesort algorithm on each half until it reaches its base case, which is when the array has only one element. At this point, the single element is considered to be sorted.

Finally, after each half is sorted, the elements of the two halves are merged together. This is done by comparing the elements of each half and placing them in the correct order in a new array. This process is repeated until all of the elements are in the new array and the sorting is complete.

Overall, Mergesort is an efficient sorting algorithm that uses a divide and conquer approach. It is stable and easy to implement, making it a popular choice for many applications.

Mergesort Pseudocode

Mergesort can be described in pseudocode as follows:

Mergesort(A, p, r):

// A is an array, p is the start index, and r is the end index

// Base case
If p ≥ r 
    return

// Find the middle index
q = (p+r)/2

// Recursively sort the left and right halves of the array
Mergesort(A, p, q)
Mergesort(A, q+1, r)

// Merge the sorted halves
Merge(A, p, q, r) 

Time Complexity

The time complexity of Mergesort depends on the size of the input array. The best-case time complexity is O(n log n), where n is the size of the array. This means that the time required to sort the array is proportional to the logarithm of the array size. The worst-case time complexity is also O(n log n). This means that the time required to sort the array does not depend on the order of the elements in the array.

The average-case time complexity is also O(n log n). This means that the time required to sort the array is proportional to the logarithm of the array size, regardless of the order of the elements in the array.

Space Complexity

The space complexity of Mergesort is O(n). This means that the amount of additional memory required to sort the array is proportional to the size of the array.

Python Implementation of Mergesort

Now that we have a basic understanding of the Mergesort algorithm, let’s look at how to implement it in Python. The following code implements the pseudocode given above:

def mergesort(arr, p, r):
    # Base case
    if p >= r:
        return

    # Find the middle index
    q = (p + r) // 2

    # Recursively sort the left and right halves of the array
    mergesort(arr, p, q)
    mergesort(arr, q + 1, r)

    # Merge the sorted halves
    merge(arr, p, q, r) 

def merge(arr, p, q, r):
    # Calculate the sizes of the subarrays
    n1 = q - p + 1
    n2 = r - q

    # Create the subarrays
    left = [0] * (n1 + 1)
    right = [0] * (n2 + 1)

    # Copy the elements of the original array into the subarrays
    for i in range(n1):
        left[i] = arr[p + i]
    for j in range(n2):
        right[j] = arr[q + j + 1]

    # Add a sentinel value at the end of each subarray
    left[n1] = float('inf')
    right[n2] = float('inf')

    # Merge the subarrays
    i = 0
    j = 0
    for k in range(p, r + 1):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1

# Test
arr = [5, 2, 4, 6, 1, 3]
mergesort(arr, 0, len(arr) - 1)
print(arr) # [1, 2, 3, 4, 5, 6]

Conclusion

In this article, we discussed Mergesort, a divide-and-conquer sorting algorithm that is widely used in computer science. We looked at the time and space complexity of the algorithm, and then provided a Python implementation. Mergesort is an efficient and reliable algorithm that is well-suited for many different applications.

Exercises

def mergesort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    mid = n // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    return merge(left, right)

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

def merge_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    mid = n // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right, arr)

def merge(left, right, arr):
    i, j, k = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1
    return arr

def merge_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    mid = n // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right, arr)

def merge(left, right, arr):
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[i + j] = left[i]
            i += 1
        else:
            arr[i + j] = right[j]
            j += 1
    while i < len(left):
        arr[i + j] = left[i]
        i += 1
    while j < len(right):
        arr[i + j] = right[j]
        j += 1
    return arr

def merge_sort(arr):
    n = len(arr)
    # Create a temporary array to store the sorted elements
    temp = [None] * n 
    # Iterate over the array by powers of two
    for block_size in range(1, n+1):
        # Iterate over the array in blocks of 'block_size'
        for start in range(0, n, block_size*2):
            # Calculate the start and end indices of the left and right subarrays
            left_start, left_end = start, min(start + block_size - 1, n-1)
            right_start, right_end = left_end + 1, min(left_end + block_size, n-1)
            # Merge the left and right subarrays
            i, j, k = left_start, right_start, left_start
            while i <= left_end and j <= right_end:
                if arr[i] <= arr[j]:
                    temp[k] = arr[i]
                    i += 1
                else:
                    temp[k] = arr[j]
                    j += 1
                k += 1
            # Copy the remaining elements into the temp array
            while i <= left_end:
                temp[k] = arr[i]
                i += 1
                k += 1
            while j <= right_end:
                temp[k] = arr[j]
                j += 1
                k += 1
        # Copy the sorted elements from the temp array back into the original array
        for i in range(n):
            arr[i] = temp[i]
    return arr

def merge_sort(arr):
    n = len(arr)
    # Iterate over the array by powers of two
    for block_size in range(1, n+1):
        # Iterate over the array in blocks of 'block_size'
        for start in range(0, n, block_size*2):
            # Calculate the start and end indices of the left and right subarrays
            left_start, left_end = start, min(start + block_size - 1, n-1)
            right_start, right_end = left_end + 1, min(left_end + block_size, n-1)
            # Merge the left and right subarrays
            i, j, k = left_start, right_start, left_start
            while i <= left_end and j <= right_end:
                if arr[i] <= arr[j]:
                    arr[k] = arr[i]
                    i += 1
                else:
                    arr[k] = arr[j]
                    j += 1
                k += 1
            # Copy the remaining elements
            while i <= left_end:
                arr[k] = arr[i]
                i += 1
                k += 1
            while j <= right_end:
                arr[k] = arr[j]
                j += 1
                k += 1
    return arr