Gráfico 1: Quick-Sort Entrada Ordenada (Tempo 0 a 11.000 segundos)

Para entrada ordenada realmente o Quick-Sort cai no seu pior caso e sua curva é uma exponencial de ordem 2 e seu uso neste caso deve ser totalmente evitado.

Gráfico 2: Quick-Sort Entrada Inversamente Ordenada (Tempo 0 a 11.000 segundos)

Como dito em sua descrição, o Quick-Sort para entrada inversamente ordenada também é muito lento se tornando quadrático pois seu Partition irá particionar o arranjo com n elementos em 2 arranjos sendo 1 com n-1 elementos e outro com apenas 1 elemento, diminuindo o problema em apenas 1 elemento.

Gráfico 3: Quick-Sort Entrada Aleatória (Tempo 0 a 11.000 segundos)

Gráfico 4: Quick-Sort Entrada Aleatória Detalhado (Tempo 0 a 1 segundo)

   
Veja também:
Explicação Teórica!
Implementação em C/C++!