Skip to main content
Practice

Implementing Merge Sort

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

Division Example
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]

2. Recursive Sorting: Recursively sort each part.​

Recursive Sorting Example
merge_sort(L)
merge_sort(R)

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

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

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.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.