Mergesort – How does it work?

• Split the input in two parts A and B of (roughly) equal size (this is the „divide“ part)

• Sort A, Sort B:

  • if the smaller list only has one or two elements, this operation is trivial
  • otherwise A and B are again splitted into smaller parts

• merge the sorted lists A and B into one sorted list (this is the „conquer“ part)