C# quicksort implementation (LeetCode Sort an Array)

Question

I implemented quick sort after merge sort as part of LeetCode question for sorting an array. The solution code can be found at https://leetcode.com/problems/sort-an-array/solutions/7180269/i-implemented-quicksort-but-is-very-slow-1q99/ .

Here is the code:

public class Solution {
// let's use quicksort
// pivot is the median of first, last, middle elements
// when the count is smaller than 25, switch to insertion sort
public int[] SortArray(int[] nums) {
 this.QuickSort(nums, 0, nums.Length - 1);
 return nums;
}
public void QuickSort(int[] nums, int l, int r) {
 if (r - l + 1 < 25) {
 this.InsertionSort(nums, l, r);
 return;
 }
 int p = this.Partition(nums, l, r);
 // pivot itself is sorted so don't touch it
 this.QuickSort(nums, l, p - 1);
 this.QuickSort(nums, p + 1, r);
}
public void InsertionSort(int[] nums, int l, int r) {
 int j;
 for (int i = l + 1; i <= r; i++) {
 j = i;
 while (j > l && nums[j] < nums[j - 1]) {
 this.Swap(nums, j, j - 1);
 j--;
 }
 }
}
// lomuta way
// put the pivot to the end, swap to be precise
// keep track of the first big number that is ready swapped with a number smaller than the pivot
// when you see a smaller number while going through the array,
// catapult it back to the tracker's big number, swap to be precise, update the tracker keep going
// once you go up until the pivot which is the last element, simply catapult the pivot itself
// to the tracker's position,
// which ends up making the pivot have smaller numbers on its left and higher on its right
// tiny optimization if
// the all the through the array is filled with smaller numbers
// you will have to swap them with themselves
// which is stupid
// so, maybe add a check for the same index 
// if yes, just update the tracker and keep going
// you see too much work here
// too much thing
// but I did it
// I understood it!!!!!!
// I know ai will just ignore this part when I ask it how well I did the solution
// I guess I am talking to myself
public int Partition(int[] nums, int l, int r) {
 // find the pivot
 int p = this.PutPivotIntoPlace(nums, l, r);
 int pivotValue = nums[p];
 // put the pivot to the end
 this.Swap(nums, r, p);
 
 // begin the catapulting
 int i = l - 1;
 for (int j = l; j < r; j++) {
 if (nums[j] <= pivotValue) {
 this.Swap(nums, i + 1, j);
 i++;
 }
 }
 // put at the right place
 this.Swap(nums, i + 1, r);
 // now pivot is at index i + 1
 return i + 1;
}
public int PutPivotIntoPlace(int[] nums,int l, int r) {
 int m = (l + r) / 2;
 // Sort the three elements so that nums[m] contains the median
 if (nums[l] > nums[m]) {
 this.Swap(nums, l, m);
 }
 if (nums[m] > nums[r]) {
 this.Swap(nums, m, r);
 if (nums[l] > nums[m]) {
 this.Swap(nums, l, m);
 }
 }
 return m;
}
public void Swap(int[] nums, int i, int j) {
 int temp = nums[i];
 nums[i] = nums[j];
 nums[j] = temp;
}
}

I implemented quick sort with insertion sort for base case. I don't see any bugs. I ran it on my laptop. Everything seemed to work as it should according to the algorithm. Input array is [110, 100, 0]. When this input is provided, LeetCode is saying the time limit exceeded. Even when it accepted it, the time was around 1800 ms while my merge sort only took around 80 ms but they have the same time complexity. I wonder why this is the case.

• toolic: Always include a sufficient description of the problem to be solved - while a link to the challenge is welcome, the review request needs to be complete when the challenge site is unavailable.
• Jesse C. Slicer: Here is a hint: Look at the end of your public void QuickSort(int[] nums, int l, int r) method and note that there are two recursive calls. Now research the concept of "tail recursion" to convert it into a non-recursive method. The performance profile will change for the better.
• Olivier Jacot-Descombes: How did you measure these times? Just using the StopWatch or comparing DateTimes is not accurate as there are a lot of pitfalls. Use BenchmarkDotNet.
• Dovud Jo'rayev: I did not measure the times. Leetcode gives the runtime itself.
• user555045: I don't see any way for this code to spend 2.3 seconds (or 1.8 seconds whatever the case may be) on just 3 elements, that's an absolute eternity: billions of operations per element. Even Bogosort is not that bad (well it's random so there's a very small chance). Surely that's not what's happening here? Also that definitely does not happen on my machine for that input.

Answer 1

This is not necessarily an answer to your question. But in order to exclude errors on LeetCode side, you better make your own measurements.

Install the BenchmarkDotNet package by right-clicking on your project and selecting Manage NuGet Packages.... (I assume that your project is a Console App. If not create one and copy your code. BenchmarkDotNet requires a Console App.)

As an example, add this class to your project:

public class SortingBenchmark
{
 private Solution _sut = new();
 [Benchmark]
 public void Sort_3_Items() => _sut.SortArray([110, 100, 0]);
 [Benchmark]
 public void Sort_30_Items() =>
 _sut.SortArray(Enumerable.Range(0, 30)
 .Select(_ => Random.Shared.Next())
 .ToArray());
 [Benchmark]
 public void Sort_300_Items() =>
 _sut.SortArray(Enumerable.Range(0, 300)
 .Select(_ => Random.Shared.Next())
 .ToArray());
 [Benchmark]
 public void Sort_3000_Items() =>
 _sut.SortArray(Enumerable.Range(0, 3000)
 .Select(_ => Random.Shared.Next())
 .ToArray());
 [Benchmark]
 public void Sort_30_000_Items() =>
 _sut.SortArray(Enumerable.Range(0, 30_000)
 .Select(_ => Random.Shared.Next())
 .ToArray());
}

And start the benchmarks in Program.cs with:

var summary = BenchmarkRunner.Run<SortingBenchmark>();

Compile the code for Release mode and start the application with Ctrl-F5 (in Visual Studio, or with a corresponding command in another IDE). This starts the application without a debugger attached.

This runs for some time and prints a lot of stuff in the console and finally this table:

| Method | Mean | Error | StdDev |
|------------------ |-----------------:|--------------:|--------------:|
| Sort_3_Items | 8.994 ns | 0.0426 ns | 0.0399 ns |
| Sort_30_Items | 563.893 ns | 0.9513 ns | 0.8899 ns |
| Sort_300_Items | 8,233.713 ns | 10.0867 ns | 8.4228 ns |
| Sort_3000_Items | 109,933.315 ns | 211.0577 ns | 187.0971 ns |
| Sort_30_000_Items | 1,386,662.350 ns | 3,207.2358 ns | 2,678.1872 ns |

The "Mean" column contains the results.

Answer 2

Most of the code presented for review is unobtrusive.

I'd prefer XML documentation comments for at least SortArray() and QuickSort() - is r inclusive or exclusive?
These are the methods conceivably used "elsewhere" - nothing else should be public.

Methods not using any instance members may better be static.

Much more time is spent reading program source code than writing it:
Try and make "the partition comment" readable as best you can.

Quicksort has been scrutinised a lot, known problems include linear growth of information to keep about work yet to do (remedy: do the smaller part first) and repeated values.

For swapping array elements see SO: How can I swap two values of an array in C#?

(One thing I'm dissatisfied with: the names i and j in Partition().
As i is used but in the form i + 1, I'd initialise a nextSmaller = l.
Not sure about toCompare -

 while (nums[nextSmaller] < pivotValue)
 nextSmaller += 1;
 for (int check = nextSmaller; check < r; check++) {
 if (nums[check] < pivotValue) {
 this.Swap(nums, nextSmaller++, check);
 }
 }
 // put pivot at the right place
 this.Swap(nums, nextSmaller, r);
 // now pivot is at index nextSmaller
 return nextSmaller;

)

Answer 3

This is a LeetCode Platform Issue, Not a Code Bug

After thorough investigation, I discovered that my QuickSort implementation is actually correct. The Time Limit Exceeded error is caused by LeetCode's biased test cases rather than algorithmic flaws.

The Smoking Gun Evidence

I tested this simple solution:

public class Solution {
 public int[] SortArray(int[] nums) {
 Array.Sort(nums);
 return nums;
 }
}

Result: Instant acceptance ✅

Meanwhile, my mathematically equivalent QuickSort with proper optimizations gets TLE ❌.

Why This Happens

LeetCode's test cases include pathological scenarios specifically designed to trigger QuickSort's worst-case O(n2) behavior:

• Large pre-sorted arrays: [1, 2, 3, ..., 50000]
• Reverse-sorted arrays: [50000, 49999, ..., 1]
• Arrays with excessive duplicates: [5, 5, 5, ...]

These patterns cause standard QuickSort (even with median-of-three) to degrade performance, while Array.Sort() uses Introsort - a hybrid algorithm that automatically switches to HeapSort when it detects QuickSort hitting worst-case scenarios. To double check, I implemented the default algorithm to see if it still causes a problem. It did not.

Code Review Conclusion

My original code review question was based on a false premise. My code doesn't have bugs.

The "failure" occurs because LeetCode's test design favors specific algorithm implementations over others, creating an unfair testing environment that contradicts the problem's general "sort an array" statement.