In comparison...

• Heapsort:

  • good complexity
  • only O(1) additional memory needed
  • data must be available from the beginning to build a heap

• Mergesort:

  • data is read sequentially, that makes it a good algorithm for sorting external data (i.e. files)
  • it is difficult to do the split-and-merge process in-place, so you need O(n) additional memory