## QuickSort (Almost like merge sort but worse).

Unlike merge sort it is somewhat weird but trust me the javascript implementation is quite easy to grasp unlike C or JAVA.It is a divide and conquer algorithm with time complexity O(nlogn) in best case and O(n^2) in worst case scenario.

So let’s get into it .

Quick review(Pun intended):

Main thing to grasp is that you take a random element , call it pivot and put it in it’s place .No exactly you put the element where it will remain for the rest of implementation.So you do that by moving all the element less than the pivot element to left and all the element greater than pivot element right of it.Now make two new arrays called left and right give them the values that are present in the left and right of the original array respectively .Now the run the sort function on them until the length of either array is 0.

After that concatenate left right array along with the pivot element in each recursion of the algo.

Algo:Step 1 :If length of input array is 0 return the array. STEP 2 :take the first element as pivot element STEP 3 : Push all the element less than the pivot element to a left array and all the element greater than pivot element to a right array STEP 4 :go to step 1 by taking an array( that is concatenation of first left then pivot element and then right array).as input.

#### Implementation in JS.

```
function qsort(arr){
if(arr.length==0)return [];
var pivot=arr[0];
var left=[],right=[];
for(var j=1;j<arr.length;j++){
if(arr[j]<pivot)
left.push(arr[j]);
else
right.push(arr[j]);
}
return qsort(left).concat(pivot,qsort(right));
}
var c=[2,3,4,5,6,7,8,3,4,43,6,6,7,8,9,5,3,5,7,89,4];
console.log(qsort(c));
```