quick sort and its time complexity

Here is the javascript implementation.

The first time run partition function. partition([4,8,7,1,3,5,6,2], 0, 7)
index is actually the swap position if any number less than 4(first item) is found

• compare 8 with 4, 8>4, no change
• compare 7 with 4, 7>4, no change
• compare 1 with 4, 1<4, swap 1 with 8 (put the less number behind 4) and index++ (count the number less than 4)
• now the array is 4,1,7,8,3,5,6,2
• compare 3 with 4, 3<4, swap 3 with 7 and index++
• now the array is 4,1,3,8,7,5,6,2
• compare 5 with 4, 5>4, no change
• compare 6 with 4, 6>4, no change
• compare 2 with 4, 2<4, swap 2 with 8 and index++
• now the array is 4,1,3,2,7,5,6,8
• it executes swap(arr, pivot, index - 1); which swaps 4 with 2.
• now the array is 2,1,3,4,7,5,6,8

As it reaches the end of the array, partition method is done, it returns 3, which is the position index of number 4 in current array.
We can see left to the 4, they are all numbers less than 4. The right side of 4 are all the numbers great than 4.
Then it will do recursive quickSort on left and right.

The worst time complexity is O(n²)

cn+c(n−1)+c(n−2)+⋯+2c=c(n+(n−1)+(n−2)+⋯+2)=c((n+1)(n/2)−1)=c((n²+n)/2-1) => O(n²)

The best time complexity is O(nlogn).

Quicksort's best case occurs when the partitions are as evenly balanced as possible: their sizes either are equal or are within 1 of each other.

Here is the dual pivot quick sort.
http://www.geeksforgeeks.org/dual-pivot-quicksort/
The basic idea is that it has two pivots, the left and the right. If the left > right, swap them. Then move anything < left to the left of left pivot and anything > right pivot to the right of the right pivot.