I remember on olympiads one trick that I though was brilliant out-of-the-box thinking was to shuffle input before sorting to avoid worst-case-prepared inputs.