lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter3Title

pythonIntroAlgorithms2Chapter4Title

def merge_sort(arr):
    if len(arr) > 1:
        # Split the array into two halves
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        # Recursively sort each half
        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        # Merge the sorted halves
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Merge the remaining elements of L and R
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

    return arr


array = [38, 27, 43, 3, 9, 82, 10]

# Execute merge sort
sorted_array = merge_sort(array)
print("Sorted array:", sorted_array)

# Implementing Merge Sort

## 1. Divide: Split the original list into two parts as evenly as possible.

```python title="Division Example"
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
```

<br />

## 2. Recursive Sorting: Recursively sort each part.

```python title="Recursive Sorting Example"
merge_sort(L)
merge_sort(R)
```

<br />

## 3. Merge: Combine the two sorted parts into one sorted list.

```python title="Merge Example"
i = j = k = 0
while i < len(L) and j < len(R):
    if L[i] < R[j]:
        arr[k] = L[i]
        i += 1
    else:
        arr[k] = R[j]
        j += 1
    k += 1

while i < len(L):
    arr[k] = L[i]
    i += 1
    k += 1

while j < len(R):
    arr[k] = R[j]
    j += 1
    k += 1
```

<br />

## Time Complexity

1. `Worst-case time complexity`: O(nlog n)

   - Merge sort maintains a consistent time complexity during the divide and merge processes. At each level, the array is split in half, and for each level, it performs \(n\) operations. Therefore, it performs a total of \(n\) operations over \( \log n \) levels.

2. `Best-case time complexity`: O(nlog n)

   - Even in the best case, merge sort proceeds with the same division and merge process, so the time complexity remains unchanged.

3. `Average time complexity`: O(nlog n)

   - In general cases, merge sort maintains a consistent time complexity of (O(n log n)). It requires the same amount of work regardless of the initial sorted state of the array.

Implementing Merge Sort