Hello,

Thank you for your time!

I am trying to understand the Quick Sort algorithm. I have some questions about the partition method. I found the following implementation online:

```
import java.util.Scanner;
public class QuickSorts
{
public static int partition(int a[], int left, int right, int size)
{
int pivot = a[left];
boolean flag =true;
while (flag)
{
if (a[left] < pivot)
{
left++;
}
if (a[right] > pivot)
{
right--;
}
if (left < right)
{
int temp = a[left];
a[left] = a[right];
a[right] = temp;
}
else
{
flag = false;
}
}
return right;
}
public static void quicksort(int a[], int left, int right, int size)
{
if (left < right)
{
int pivot = partition(a, left, right, size);
quicksort(a, left, pivot-1, size);
quicksort(a, pivot+1, right, size);
}
}
public static void main(String args[])
{
int a[] = {12,1,0,9,56,7,2,8};
int size = a.length;
System.out.print ("Starting Array:");
for (int i =0; i<size; i++)
{
System.out.print(a[i] + " ");
}
System.out.println();
quicksort(a, 0, size -1, size);
for (int i =0; i<size; i++)
{
System.out.print(a[i] + " ");
}
}
}
```

So far, I understand the following:

1) The quicksort is a process of placing the pivot(left most value in this program) in the appropriate cell# of the input array such that values to its left < pivot and values to the right > pivot

2) The quick sort method calls the partition method (as described above) recursively on both sub-arrays of the pivot.

Step#2 makes sense. The objective of the partition method in Step#1 makes sense as well, but not the logic of how it works. When I printed the input array inside the while loop of the partition method, I get the following:

Starting Array:12 1 0 9 56 7 2 8

8 1 0 9 56 7 2 12

8 12 0 9 56 7 2 1

8 1 0 9 56 7 2 12

8 1 12 9 56 7 2 0

8 1 0 9 56 7 2 12

8 1 0 12 56 7 2 9

8 1 0 9 56 7 2 12

8 1 0 9 12 7 2 56

8 1 0 9 2 7 12 56

8 1 0 9 2 12 7 56

8 1 0 9 2 7 12 56

8 1 0 9 2 7 12 56

This clearly works and is very elegant in its implementation.There is no way I could have written this method from scratch!

I would have used two arrays, one to store values < pivot and the other values > pivot and copied it back to the original array into the proper cells. But the space complexity of my method would be O(n), which is clearly inferior to the O(1) of the above implementation.

If possible, could you explain me the idea behind writing the partition as mentioned above?

Thank you!