Unexpected Infinite Loop in Iterative QuickSort Implementation in C# - Need Debugging guide
I'm currently working on an iterative implementation of the QuickSort algorithm in C# and I've run into an unexpected infinite loop situation. My implementation is supposed to sort an array of integers. However, when I test it with certain datasets, it just keeps running without terminating. Here's the simplified version of the code I've written: ```csharp void IterativeQuickSort(int[] array) { Stack<(int, int)> stack = new Stack<(int, int)>(); stack.Push((0, array.Length - 1)); while (stack.Count > 0) { var (start, end) = stack.Pop(); if (start >= end) continue; int pivotIndex = Partition(array, start, end); stack.Push((start, pivotIndex - 1)); stack.Push((pivotIndex + 1, end)); } } int Partition(int[] array, int start, int end) { int pivot = array[end]; int i = start - 1; for (int j = start; j < end; j++) { if (array[j] <= pivot) { i++; Swap(array, i, j); } } Swap(array, i + 1, end); return i + 1; } void Swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } ``` I suspect the scenario might be with my partitioning logic, but I've checked a few times and need to find anything that jumps out. The infinite loop appears to happen when the pivot is not partitioning the elements correctly, leading to repeated states in the stack. For example, when I run it with the array `{4, 3, 2, 1, 0}`, it just keeps iterating. I've tried adding debug logs inside the while loop to print the values of `start`, `end`, and `pivotIndex`, but they don't seem to give any indication of why it hangs. Can someone guide to figure out where my implementation might be going wrong? Any insights would be appreciated! What am I doing wrong?