Quick sort

This method takes an array or subarray into consideration. It invokes the method to find the pivot of the array or subarray and splits the array or subarray on the basis of the pivot. Here is its syntax:

Quick Sort (arr,n)

Here, arr is the array consisting of n elements.

This is how we use this method:

1. Let l=1 and u=n, where l and u represent the lower and upper index location, respectively, of the array.
2. Push l into stack1.
3. Push u into stack2.

4. While stack1 or stack2 is not empty, repeat steps 5 through 10.
5. Pop the lower index location of the array from stack1 into variable s, that is, s becomes the lower index location of the array to be sorted.
6. Pop the upper index location from stack2 into the variable e, that is, the e variable will get the upper index location of the array.
7. Find out the pivot by invoking the FindingPivot method as follows:

pivot=FindingPivot(arr,s,e)

Recall that a pivot point is an index location in the array where the elements smaller than the pivot are before it and elements larger than the pivot are after it. The array is split at the pivot point and the quick sort method is recursively applied on the two halves individually.

8. Once the pivot is known, divide the array into two halves. One array will have values from s (the lower index location) to pivot-1, and another array with the elements ranges from pivot+1 to e (the upper index location).
9. For the first half of the array, push s into stack1 and pivot-1 into stack2.
10. For the second half of the array, push pivot+1 into stack1 and e into stack2.