0-Introduction

Introduction

Quicksort is most widely used sorting algorithm than any other algorithm.

Invented in 1960 by C.A.R. Hoare.

  • easy to implement
  • resource efficient in many cases

features

  • in-place
  • $N \log N $ on avg case

drawbacks

  • Not stable
  • $N^2$ in worst case
  • fragile ( any small mistake in implementation can go un-noticed and cause bad performance)

STL library uses qsort function.

Performance of the quicksort is highly dependent on the input.