# Quicksort implementation in java

It was about time I made myself a blog. I will write in english to be able to
reach out to as many as possble. The first thing that came to my mind to
publish, was a quicksort implementation in java I recently wrote.

Quicksort is pretty fast. And runs in O(n lg n) on average.

I wrote it for educational purposes. If you need to sort something in java, you should probably use Arrays.sort, which can sort objects that implements the Comparable interface.

```
public static void quicksort(int[] a, int low, int high) {
if(low < high) {
int pivot = partition(a, low, high);
quicksort(a, low, pivot - 1);
quicksort(a, pivot + 1, high);
}
}
// randomized partition
public static int partition(int[] a, int low, int high) {
int i = low;
int pivotIndex = (int) Math.random() * (high-low);
int tmp = a[low + pivotIndex];
a[low + pivotIndex] = a[high];
a[high] = tmp;
int pivot = a[high];
for(int j = low; j < high; j++) {
if(a[j] <= pivot) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i += 1;
}
}
tmp = a[i];
a[i] = a[high];
a[high] = tmp;
return i;
}
```