Worst case is O(n). Think about it; recursing on one half after finding a pivot which turns out to be the smallest or largest (presuming you recurse on both halves).

A malicious attacker may even craft data that causes this behaviour, if they know the library / variant being used.