Quicksort implementation in Java

I wrote this implementation of quicksort as a bit of practice and review for myself. I did not base my algorithm on anything more than my own understanding of quicksort and working through a couple of examples myself on paper, so please let me know of any improvements or optimizations that I could make!

```
import java.util.ArrayList;
import java.util.Collections;
import java.util.concurrent.ThreadLocalRandom;

/**
* A simple, generic, in-place implementation of quicksort
* @implNote The pivot used during the partitioning step is selected at random
*/
public class Quicksort {

/**
* Sort the given array using quicksort
* @param arr Array to sort
* @param Type of the elements contained by arr
*/
public static void sort(ArrayList arr) {
sort(0, arr.size() - 1, arr);
}

/**
* Sorts a designated section of the given array using quicksort
* @param left Lower-bound index of section (inclusive)
* @param right Upper-bound index of section (inclusive)
* @param arr Array to perform sort within
* @param Type of the elements contained by arr
*/
private static void sort(int left, int right, ArrayList arr) {
// Exit if section contains only a single element, or is invalid
if (right - left Type of the elements contained by arr
* @return The final index of the partition value
*/
private static int partition(int left, int right, int pivot, ArrayList arr) {
// Move pivot to left-most position (get out of the way)
Collections.swap(arr, left, pivot);
pivot = left;

// Perform partitioning
int rightPartitionStart = left + 1;
for (int i = left + 1; i <= right; i++) {
// If our current value is less than our pivot, move it into the left partition
if (arr.get(i).compareTo(arr.get(pivot)) < 0) {
Collections.swap(arr, i, rightPartitionStart);
rightPartitionStar

1

I would declare void sort(ArrayList arr) as > void sort(ArrayList arr)

2

void sort(int left, int right, ArrayList arr) {
    ...
}

I suggest you make it public and reorganize the arguments like this:

void sort(ArrayList arr, int fromIndex, int toIndex)

where fromIndex corresponds to left in your version, and toIndex corresponds to right + 1: these are the conventions in JDK's sort algorithms, so that toIndex is an exclusive upper bound.

3

I would make the three-parameter version public since sometimes people want to sort only a subrange of an array (or ArrayList in our case).

4

Declare the constructor as private:

private Quicksort() {}

Hope that helps.

StackExchange Code Review Q#123971, answer score: 3