Merge Sort

8.1 Definition of Merge Sort

Merge Sort is an efficient, stable, and comparison-based sorting algorithm that uses a "divide and conquer" approach to organize elements. The algorithm splits an array into two halves, recursively sorts each half, and then merges the sorted halves into one sorted array.

How it works:

Divide:

• Split the original array in half to get two subarrays.
• Repeat the process for each subarray until each subarray is an array of one element (or empty).

Merge:

• Merge two neighboring subarrays into one sorted array.
• Repeat the merging process until one sorted array is obtained.

Time and space complexity of Merge Sort

Time complexity:

• In the worst case: O(n log n)
• On average: O(n log n)
• In the best case: O(n log n)

Space complexity:

O(n) — extra space needed to store temporary subarrays.

8.2 Top-Down Merge Method

The initial sequence is recursively split into halves until we get subsequences of 1 element each. From the obtained subsequences, we form ordered pairs using the merge method, then ordered quads, and so on.

Let's consider a sequence:

Split the sequence into 2 halves (recursively, until we get pairs).

Each subsequence is sorted using the merge method and we get the final sequence.

8.3 Implementation of the Merge Sort Algorithm

This is where recursion comes in handy! It's a very good and fast algorithm compared to previous ones. It splits the array in half, sorts both parts separately, and then quickly merges the sorted parts.

Its implementation looks something like this:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Find the middle of the array
        left_half = arr[:mid]  # Split the array into two subarrays
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Recursively sort the left half
        merge_sort(right_half)  # Recursively sort the right half
        
        i = j = k = 0
        
        # Merge the sorted halves
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # Check for remaining elements
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# Example usage:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)
# Output: Sorted array: [3, 9, 10, 27, 38, 43, 82]

The key point at the very beginning:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Find the middle of the array
        left_half = arr[:mid]  # Split the array into two subarrays
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Recursively sort the left half
        merge_sort(right_half)  # Recursively sort the right half

Here's what's happening there:

1. We find the middle of the array
2. Split the array into 2 parts
3. Sort each part separately

This approach significantly speeds up the algorithm.

2

Task

Python SELF EN, level 58, lesson 3

Locked

Merging Arrays

Merging Arrays

Open

2

Task

Python SELF EN, level 58, lesson 3

Locked

Merge Sort

Merge Sort

Open