Merge sort...

Here are the basic characteristics:

  1. Divide and conquer algorithm
  2. Stable
  3. NOT in place
  4. Running time is always O(n log n)