You are given a custom sorting algorithm that has O(n²) time complexity in the worst case. Your task is to analyze the algorithm, identify the bottlenecks, and modify it to achieve O(n log n) average time complexity while maintaining the same functionality. Provide: 1) Original algorithm pseudocode with complexity analysis 2) Your optimized algorithm with pseudocode 3) Complexity analysis of your solution 4) Proof of correctness 5) Discussion of trade-offs in your approach