2.3.2 quick sort

• Three quick heapSort, MergeSort, quickSort. (Olog(n))
• MergeSort need O(N) extra space. When you merge two lists, this shortcoming can be avoid
• partition
  /* This function takes last element as pivot, places 
     the pivot element at its correct position in sorted 
      array, and places all smaller (smaller than pivot) 
     to left of pivot and all greater elements to right 
     of pivot */ 
  partition (arr[], low, high){ 
      // pivot (Element to be placed at right position) 
      pivot = arr[high]; 
      i = (low - 1)  // Index of smaller element 
      for (j = low; j <= high- 1; j++)    { 
          // If current element is smaller than or 
          // equal to pivot 
          if (arr[j] <= pivot)        { 
              i++;    // increment index of smaller element 
              swap arr[i] and arr[j] 
          } 
      } 
      swap arr[i + 1] and arr[high]) 
      return (i + 1) 
  }

  
  
  

• Quick sort need random access ability.