What does pathological input mean with respect to sorting algorithms?

Question

I was reading about quick sort's time complexity when I saw that although it's n log n , it reduces to n^2 for pathological inputs. When I go and check what a pathological input means in this context, I read on wikipedia (and a couple other blogs) that in Computer Science, a pathological input is any input that violates the normal complexity or the correctness of an algorithm! Well, this is kind of cyclic. What exactly is a pathological input in this context?

Answer 1

It may be more suited to English (or some other etymology-related) SO site, but pathological comes from Greek, and means the study of ailments or suffering (also emotions, since ancient Greeks were famous for correlating the two...), and in this context - all sorts of disruptions to the normal order of things.

Hence, a pathological case for an algorithm is the worst possible input it may have to work on, one that is so disrupted or badly arranged that it makes you work the hardest to perform your task over. The worst case execution complexity is derived from that and is usually used to describe the algorithm complexity for an unknown data. In some cases, when the worst case is really obscure or unlikely, it's also ok to talk about the common case complexity and find algorithms that optimize that.

For a quicksort algorithm, it would be an input that happens to have all the pivots you choose (whether randomly or with some other method), map to one of the sides of your current section, rendering the sort process always go through the worst path in terms of steps.

Answer 2

Many sorting algorthms have issues with data that is

1. Already sorted
2. Already sorted in the reverse direction
3. All the same (which also includes #1 and #2)

I found this page that looks interesting with visual comparisons of various sorts