/**
 * Java implementation of quick sort
 *
 * @author Tibeyev Timur (timurtibeyev@gmail.com)
 */

public class QuickSort {

    /**
     * Method responsible for sorting array.
     *
     * @param arr   array of elements
     * @param left  start of the segment to sort
     * @param right end of the segment to sort
     */
    private void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int i = left;
        int j = right;

        int mid = (i + j) / 2;
        // Pivot element
        int v = arr[mid];

        while (i < j) {
            // Find element from the left side, which is equal or greater than pivot element
            while (arr[i] < v) {
                i++;
            }

            // Find element from the right side, which is equal or less than pivot element
            while (v < arr[j]) {
                j--;
            }

            // If such elements exist, perform swapping
            if (i