Quick Sort

Quick sort runs O(nlogn). It is similar with merge sort, but it differs by selecting a pivot and partition the array based on the pivot element.
Let's look at an example.
We have an integer array {7,5,9,10,1,6,13,2,8},  and choose pivot element. In this case we choose pivot as the last element, i.e., 8.
The rearrange the left and right based on pivot.

use index i=0, j=array.length-1
{7,5,2,6,1}            {8}              {10,13,9}
{}  {1} {7,5,2,6}   {8}              {}  {9}  {10,13}
{1} {2,5} {6} {7}  {8}              {9} {10} {13}
{1} {2} {5} {6} {7}  {8}           {9} {10} {13}
{1,2,5,6,7,8,9,10,13}

The code in Java is in the below. Please be careful when you partition the array based on the pivot.
For example, if you partition an array {5,3,7}, and set the pivot as the last element, it end up with i=1,j=1, and pivot = 7. Here, you only swap if the pivot is less than i-th element.

 import java.io.*;
 class myCode
 {
   public static void main (String[] args) throws java.lang.Exception
   {
     System.out.println("Hello Java");
     int[] input = {5,7,9,10,1,6,13,2,8};
     quickSort(input, 0, input.length-1);
     System.out.println("sorted list:");
     for (int i=0;i<input.length;i++) {
       System.out.print(input[i] + ",");
     }
   }
   public static void quickSort(int[] array, int start, int end) {
     if (end - start < 1) {
       return;
     } else if ((end - start) == 1) {
       if (array[start] > array[end]) {
         int temp = array[start];
         array[start] = array[end];
         array[end] = temp;
       }
     } else {
       partition(array, start, end);
     }
   }
   public static void partition(int[] array, int start, int end) {
     int pivot = array[end];
     int i=start;
     int j=end-1;
     while (i<j) {
       if (array[i]>pivot && array[j] < pivot) {
         int temp = array[i];
         array[i] = array[j];
         array[j] = temp;
         i++;
         j--;
       } else if (array[i] < pivot) {
         i++;
       } else if (array[j] > pivot) {
         j--;
       }
     }
     //swap i to end
     if (array[i] > array[end]) {
       int temp2 = array[i];
       array[i] = array[end];
       array[end] = temp2;
     }
     quickSort(array,start,i);
     quickSort(array,i+1,end);
   }
 }