Python Merge Sort in Place Fix

Code Analysis

The provided Python code includes an implementation of the merge sort algorithm to sort an array. The issue arises because the array is not being sorted in place correctly. The algorithm logic is correct, but the result is not reflected in the original array passed to the function.

Review Previous Attempts

The code attempts to perform the merge sort algorithm recursively but fails to update the original array with the sorted values.

Develop a Solution

To resolve the issue, we need to return the sorted array from each recursive call and update the original array with the sorted values at each level of recursion.

Code Development (Python)

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]
        
        # Recursive calls to sort left and right halves
        merge_sort(left_half)
        merge_sort(right_half)
        
        i = j = k = 0
        
        # Merge two halves back into the original array
        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
        
        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

# Example Usage
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array:", arr)

Code Usage Example

# Example Usage
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array:", arr)

By returning the sorted arrays and updating the original array in each recursion level, the algorithm now correctly sorts the array in place.