Inconsistent Output with Quick Sort in Python - implementing Pivot Selection Strategy
I've searched everywhere and can't find a clear answer. I'm converting an old project and I need help solving I've been struggling with this for a few days now and could really use some help. I'm implementing the Quick Sort algorithm in Python, but I'm running into an scenario where the output is inconsistent depending on the pivot selection strategy I'm using. When I choose the first element as the pivot, it works fine for small arrays, but for larger datasets, particularly those that are already sorted or nearly sorted, the performance degrades significantly and the recursion depth exceeds the limit, throwing a `RecursionError: maximum recursion depth exceeded in comparison`. To address this, I tried using the median-of-three method for pivot selection, but even then, I noticed unexpected behavior with certain input arrays. Here's my current implementation: ```python def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[0] # Change this to use median-of-three strategy less = [x for x in arr[1:] if x <= pivot] greater = [x for x in arr[1:] if x > pivot] return quick_sort(less) + [pivot] + quick_sort(greater) ``` When I test the function with the following sorted array: ```python sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] print(quick_sort(sorted_array)) ``` I get correct results, but performance optimization arise with larger datasets. I also attempted to implement a cutoff to switch to insertion sort for small subarrays, but that didn't seem to improve the situation much. Is there a better pivot selection method or a way to optimize the recursive calls? What other strategies can I employ to improve performance and ensure consistent results across different input cases? I'd really appreciate any guidance on this. Any ideas how to fix this? Has anyone else encountered this? Thanks for your help in advance! Is there a better approach? I'd really appreciate any guidance on this.