Quicksort

• like Heapsort and Mergesort, Quicksort is a „divide and conquer“ algorithm:

  • choose an element e of the input sequence (the pivot element)
  • split the input sequence in two parts:
    • the elements that are less than e
    • the elements that are greater than e
  • sort (1) and (2) recursively