Merge sort

Facts

• Invented by John von Neumann in 1945
• Stable sorting algorithm
• Best- and worst-Case performance O(n*log(n))
• Divide and Conquer algorithm
• Implementation:
  1. If there is only one item in the list, return the list
  2. Divide the unsorted list recursively into 2 sublists of equal size (so-called runs) until the list can no longer be divided
  3. Repeatedly merge sublists to produce new sorted sublists until there is only one sorted list remaining
• Effective Usages:
  1. Data structures without direct access to elements (linked lists)
  2. External sorting if RAM is too small
• Derivative Timsort (from merge sort and insertion sort): Recognize already sorted parts of the list and use them to create the sublists --> best-case performance O(n)