Quicksort implementation correctness

Question

Is there any case where this implementation might fail? I understand that it might run very slowly for some cases, but the my worry for now is more about correctness

class QuickSort {
public int findpivot(int []nums, int start, int end) {
    int pivot = nums[start];
    int left = start+1;
    int right = end;
    while(left<=right) {
        while(left<=right && nums[left]<=pivot)
            left++;
        while(left<=right && nums[right]>pivot)
            right--;
        if(left<right) {
            var tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }
    }
    int tmp = nums[right];
    nums[right] = nums[start];
    nums[start] = tmp;
    return right;
}
public void sort(int []nums, int start, int end) {
    if(start<end) {
        int pivot = findpivot(nums, start, end);
        sort(nums,start,pivot-1);
        sort(nums,pivot+1,end);
    }
}
public int[] sortArray(int[] nums) {
   sort(nums,0,nums.length-1);
   return nums;
}

Answer 1

This implementation correctly sorts arrays.

It is a mix of ideas from Hoare's and Lomuto's algorithms:

• The pivot value's location is excluded from the range that is iterated, and after the loop completes, it is swapped into position -- between the partitions -- so that the function can return the index that separates the two partitions and which has the pivot value. That means the caller can exclude this index from recursive calls. This is a principle that is used by Lomuto's algorithm.
• The loop uses two indices that approach each other from both ends of the loop's range, ensuring that the values that are outside of this shrinking window are located in the correct partition: this implements Hoare's algorithm.

Some worry could arise about the last swap, because left and right could either be equal or could have overtaken each other. First of all, we can be sure the outer loop executes at least once, because the findPivot function is only called when start<end. When the loop ends, we can be sure that right is a valid index, i.e. we have start<=right<=end. We can also be sure nums[right]<=pivot because either right==start (and nums[start]==pivot) or right is an index that was already processed with left. Therefore the final swap will move that value to the correct partition.

With these observations we can say the algorithm will correctly sort an array.

One of the things to do to ensure the code is correct, is to stress test it with random input of differing sizes.

Here is some code that does that:

    for (int size = 0; size < 50; size++) {
        System.out.println("Testing with arrays of size " + size);    
        int[] nums = new int[size];
        // Make array list with sorted values
        List<Integer> lst = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            lst.add(i);
        }
        for (int c = 0; c < 100; c++) {
            // Shuffle
            Collections.shuffle(lst);
            for (int i = 0; i < size; i++) {
                nums[i] = lst.get(i);
            }
            qs.sortArray(nums);
            // Verify
            for (int i = 0; i < size; i++) {
                if (nums[i] != i) System.out.println("ERROR");
            }
        }
    }
    System.out.println("Tests completed");