content: // Quick Sort implementation in Java
  // Time Complexity: O(n log n) average, O(n²) worst case
  // Space Complexity: O(log n)
  
  public class QuickSort {
  
      public static void quickSort(int[] arr, int low, int high) {
          if (low < high) {
              // Find the partition index
              int pi = partition(arr, low, high);
  
              // Recursively sort elements before and after partition
              quickSort(arr, low, pi - 1);
              quickSort(arr, pi + 1, high);
          }
      }
  
      private static int partition(int[] arr, int low, int high) {
          // Choose the rightmost element as pivot
          int pivot = arr[high];
          int i = low - 1; // Index of smaller element
  
          for (int j = low; j < high; j++) {
              // If current element is smaller than or equal to pivot
              if (arr[j] <= pivot) {
                  i++;
                  // Swap arr[i] and arr[j]
                  int temp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = temp;
              }
          }
  
          // Swap arr[i+1] and arr[high] (or pivot)
          int temp = arr[i + 1];
          arr[i + 1] = arr[high];
          arr[high] = temp;
  
          return i + 1;
      }
  
      // Utility method to print array
      public static void printArray(int[] arr) {
          for (int value : arr) {
              System.out.print(value + " ");
          }
          System.out.println();
      }
  
      // Main method for testing
      public static void main(String[] args) {
          int[] arr = {64, 34, 25, 12, 22, 11, 90};
  
          System.out.println("Original array:");
          printArray(arr);
  
          quickSort(arr, 0, arr.length - 1);
  
          System.out.println("Sorted array:");
          printArray(arr);
      }
  }
  