Algorithms and Data Structures - Merge Sort

Characteristics

• Time complexity:
  • Best: Ω(n log(n))
  • Average: Θ(n log(n))
  • Worst: O(n log(n))
• Space complexity:
  • Using arrays: O(n)
  • Using linked lists (and Recusion): O(log(n))
• Not in-place
• Stable

Demos:

• With Arrays
• With Linked Lists
• With Parallelism

Demonstration

• Algorithm Visualizer
• Algorithm Visualizer

References

• Other Algorithms & Data Structures