Merge sort

Strutture dati e algoritmi in Python

Miriam Antona

Software engineer

Merge sort

Follows divide and conquer
- Divide
  - divides the problem into smaller sub-problems
- Conquer
  - sub-problems are solved recursively
- Combine
  - solutions of sub-problems are combined to achieve the final solution

Merge sort - in action

A schematic representation of a list with unordered numbers.

Merge sort - in action

A schematic representation of a list with unordered numbers. The list has been divided into two parts.

Merge sort - in action

A schematic representation of a list with unordered numbers. The list has been divided into two parts. The are two new lists, the first one has the left half of the original list and the second one has the right half of the original list.

Merge sort - in action

A schematic representation of a list with unordered numbers. The new lists have been divided into two parts.

Merge sort - in action

A schematic representation of a list with unordered numbers. There are new lists with the divisions of the last divided lists.

Merge sort - in action

A schematic representation of a list with unordered numbers. The new lists have been divided into two parts.

Merge sort - in action

A schematic representation of a list with unordered numbers. There are new lists with the divisions of the last divided lists.

Merge sort - in action

A schematic representation of a list with unordered numbers. The new lists have been divided into two parts.

Merge sort - in action

A schematic representation of a list with unordered numbers. The new lists have been divided into two parts.

Merge sort - in action

A schematic representation of a list with unordered numbers. The elements from the last divided lists have been sorted.

Merge sort - in action

A schematic representation of a list with unordered numbers. The elements from the last divided lists have been merged and ordered.

Merge sort - in action

A schematic representation of a list with unordered numbers. The elements from the last divided lists have been merged and ordered.

Merge sort - in action

A schematic representation of a list with unordered numbers. The elements from the last divided lists have been merged and ordered. All the elements are sorted.

Merge sort - implementation

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]

Merge sort - complexity

Worst case: $O(n\log{}n)$
- significant improvement over bubble sort, selection sort, and insertion sort
- suitable for sorting large lists
Average case: $\Theta(n\log{}n)$
Best case: $\Omega(n\log{}n)$
- other algorithms (e.g. bubble sort, insertion sort) have better best case complexity
Space complexity: $O(n)$
- worst space complexity than other algorithms with $O(1)$
Other variants reduce this space complexity

Let's practice!

Strutture dati e algoritmi in Python