import java.util.*;

public class DivideConquerQuickSortIK {

static ArrayList<Integer> quick_sort(ArrayList<Integer> arr) {

helper(arr, 0, arr.size() - 1);

return arr;

}

static void helper(ArrayList<Integer> arr, int start, int end) {

if (start >= end) {

return;

}

// Randomly select a pivot

Random random = new Random();

int pivotIndex = random.nextInt(end - start + 1) + start;

int pivot = arr.get(pivotIndex);

System.out.println(pivot);

// Move pivot to the start

Collections.swap(arr, pivotIndex, end);

int i = start - 1; // Pointer for the smaller element

// Iterate through the array

for (int j = start; j < end; j++) {

if (arr.get(j) <= pivot) {

i++;

Collections.swap(arr, i, j);

}

}

// Place the pivot in its correct position

Collections.swap(arr, i + 1, end);

// Recursively sort the subarrays

helper(arr, start, i);

helper(arr, i + 2, end);

}

}