 This can be done efficiently in linear time and in-place.The lesser and greater sublists are then recursively sorted.This yields average time complexity of O("n" log "n"), with low overhead, and thus this is a popular algorithm.