less than 1 minute read

  • In terms of decision trees, we assume without loss of generality that all elements are distinct.
  • A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size.
  • any correct sorting algorithm must be able to produce each permutation of its input, each of the n! permutations on n elements must appear as one of the leaves of the decision tree for a comparison sort to be correct
  • Corollary 8.2: Heapsort and merge sort are asymptotically optimal comparison sorts.
    —— CLRS

4eef5df9b33bc1d137421c44a2f62241.png Tips for this figure:

  • The algorithm shown in this figure is insertion sort where we iterate j and i = j - 1


  • the worst-case comparisons for a comparison algorithm = the height of the decision tree



Leave a comment