How to implement a stable QuickSort algorithm in JavaScript

Question

How can I write a stable implementation of the Quicksort algorithm in JavaScript?

Kaminsky

Just FYI, if you write your own it will be definitely a lot slower than a native method. Do you absolutely need stable sorting? – Monetta

BTW, you ask for a "stable" implementation of quicksort, but quicksort is not an inherently stable sort. Efficient implementations will not be stable. – Teacart

Also why do you care if it's quicksort or not? Looks like merge sort is becoming the defacto en.wikipedia.org/wiki/… – Monetta

Rosetta Code is a good go-to resource for stuff like this. – Intercessor

Answer 1

You can easily "stabilize" an unstable sort using a decorate-sort-undecorate pattern

function stableSort(v, f)
{
    if (f === undefined) {
        f = function(a, b) {
            a = ""+a; b = ""+b;
            return a < b ? -1 : (a > b ? 1 : 0);
        }
    }
    var dv = [];
    for (var i=0; i<v.length; i++) {
        dv[i] = [v[i], i];
    }
    dv.sort(function(a, b){
              return f(a[0], b[0]) || (a[1] - b[1]);
            });
    for (var i=0; i<v.length; i++) {
        v[i] = dv[i][0];
    }
}

the idea is to add the index as last sorting term so that no two elements are now "the same" and if everything else is the same the original index will be the discriminating factor.

Dynamoelectric

...Though this could be more space-efficient by pushing/popping elements, and just storing i separately. – Teacart

This is far slower than this rawgithub.com/escherba/algorithms-in-javascript/master/src/… – Adowa

This is the only answer here that understands what it means to stabilize a sort. I didn't use your code, but the pattern is simple and no overhead. – Agitate

Answer 2

Quicksort (recursive)

function quicksort(array) {
  if (array.length <= 1) {
    return array;
  }

  var pivot = array[0];
  
  var left = []; 
  var right = [];

  for (var i = 1; i < array.length; i++) {
    array[i] < pivot ? left.push(array[i]) : right.push(array[i]);
  }

  return quicksort(left).concat(pivot, quicksort(right));
};

var unsorted = [23, 45, 16, 37, 3, 99, 22];
var sorted = quicksort(unsorted);

console.log('Sorted array', sorted);

Estranged

Note for those who are concerned about memory usage - this implementation doesn't perform the sort "in place"; i.e. it will use lots of extra memory. I do like its simplicity, though! – Sickroom

Stylistically speaking, I'm curious what others think about using the conditional operator for control flow (i.e. instead of assignment). Personally, I think a standard if/else is a lot more readable. – Sickroom

It's not recommended to choose the first element to be the pivot, since this could result in poor performance, even worst-case O(n^2) time complexity. A random pivot leads to better average-case performance and reduces the likelihood of worst-case performance. – Melnick

@JohnnyKontrolletti, you're correct but array[0] could be a random number since the array is not sorted. If the array is sorted, quick sort will still try to sort it and it will be O(n^2). – Sundaysundberg

Answer 3

1. Put your objects into an array.

2. Call Array.sort(). It's very fast.

   var array = [3,7,2,8,2,782,7,29,1,3,0,34];
   array.sort();
   console.log(array); // prints [0, 1, 2, 2, 29, 3, 3, 34, 7, 7, 782, 8]
   

Why does that print in lexicographic order? That's how array.sort() works by default, e.g. if you don't provide a comparator function. Let's fix this.

    var array = [3,7,2,8,2,782,7,29,1,3,0,34];
    array.sort(function (a, b)
    {
        return a-b;
    });
    console.log(array); // prints [0, 1, 2, 2, 3, 3, 7, 7, 8, 29, 34, 782]

Teacart

call Array.sort(function (a, b){return a - b;}); to sort numerically. – Metacarpal

this is not guaranteed stable sort, it is browser implementation specific – Vitals

Matt, as K Ivanov stated array.sort is browser dependent and cannot be guaranteed. I was looking for some code that I would have complete control over. – Kaminsky

@flavour404: If you want to have complete control, write your own function. – Infrasonic

@Felix: especially since the OP requests stability in a quicksort implementation. – Teacart

Btw Wikipedia says: Quicksort (also known as "partition-exchange sort") is a comparison sort and, in efficient implementations, is not a stable sort. (edit: just saw that you also commented this on the OP's question ;)) – Infrasonic

Array.sort is absolutely SLOW. A simple quicksort implementation is far faster, here is one rawgithub.com/escherba/algorithms-in-javascript/master/src/… – Adowa

@Adowa that's not true in every case, nor is quicksort the fastest in every case. Here's a benchmark comparing native with the sort algorithms in that repo: jsperf.com/sort-algorithms/21 – Teacart

@MattBall I think that test is wrong, he should create 1 new array for each test. Adaptative sort is way too fast, like it is O(n) (already sorted arrays). Running locally quicksort is by far the fastest one on Chrome 28, Windows 8... Locally, Array.sort is not the slowest, but is not really good... – Adowa

@MattBall here my tests: jsfiddle.net/Ygf3c (this one abuse features, the "raw version" (github link) is much faster) – Adowa

quicksort vs Array.sort are not comparable, the former is a sorting algorithm, the latter is sort function. You'd need to look at the implementation code of Array.sort for your specific javascript execution environment to compare. Either way, this answer is incorrect since the question ask specifically for a stable quicksort algorithm. – Peduncle

Answer 4

Quick Sort (ES6)

function quickSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = arr[Math.floor(Math.random() * arr.length)];

  let left = [];
  let right = [];
  let equal = [];

  for (let val of arr) {
    if (val < pivot) {
      left.push(val);
    } else if (val > pivot) {
      right.push(val);
    } else {
      equal.push(val);
    }
  }
  return [
    ...quickSort(left),
    ...equal,
    ...quickSort(right)
  ];
}

// Unsorted Array
const arr = [6,9,2,5,0,7,3,1,8,4];

console.log(quickSort(arr)); // [0,1,2,3,4,5,6,7,8,9]

---

Few Notes

• A random pivot keeps the algorithm efficient even when the data is sorted.
• As much as it is nice to use Array.filter instead of using for of loop, like some of the answers in this thread, it will increase time complexity (Array.reduce can be used instead, though).

Fiann

It's a quickSort but not stable. en.wikipedia.org/wiki/Sorting_algorithm#Stability – Agitate

@PeterBrand as you said, it is a quick sort. I never said it's a "stable" one though. You are more than welcome to suggest your own version. – Fiann

The OP specifically asked for a 'stable' version, and that is what I was looking for. A search for that topic lead me here. I had to read thru your code to figure out whether it answered the question. No need for me to provide an answer tho, it has been provided by @Dynamoelectric in this thread. – Agitate

why would you introduce equal and increase space complexity if you can check those in any case above in the for loop... – Vedic

Answer 5

A Functional equivalent

In celebration of Functional Javascript, which appears to be the in thing

at the moment, especially given ES6+ wonderful syntactic sugar additions. Arrow functions and destructuring I propose a very clean, short functional equivalent of the quicksort function. I have not tested it for performance or compared it to the built-in quicksort function but it might help those who are struggling to understand the practical use of a quicksort. Given its declarative nature it is very easy to see what is happening as oppose to how it works.

Here is a JSBin version without comments https://jsbin.com/zenajud/edit?js,console

function quickSortF(arr) {
    // Base case
    if (!arr.length) return []

    // This is a ES6 addition, it uses destructuring to pull out the 
    // first value and the rest, similar to how other functional languages
    // such as Haskell, Scala do it. You can then use the variables as 
    // normal below
    const [head, ...tail] = arr,
          // here we are using the arrow functions, and taking full 
          // advantage of the concise syntax, the verbose version of
          // function(e) => { return e < head } is the same thing
          // so we end up with the partition part, two arrays,
          // one smaller than the pivot and one bigger than the 
          // pivot, in this case is the head variable
          left = tail.filter( e => e < head),
          right = tail.filter( e => e >= head)

       // this is the conquer bit of divide-and-conquer
       // recursively run through each left and right array
       // until we hit the if condition which returns an empty
       // array. These results are all connected using concat,
       // and we get our sorted array.
       return quickSortF(left).concat(head, quickSortF(right))           

}

const q7 = quickSortF([11,8,14,3,6,2,7]) 
//[2, 3, 6, 7, 8, 11, 14]
const q8 =  quickSortF([11,8,14,3,6,2,1, 7])
//[1, 2, 3, 6, 7, 8, 11, 14]
const q9 = quickSortF([16,11,9,7,6,5,3, 2])
//[2, 3, 5, 6, 7, 9, 11, 16]

console.log(q7,q8,q9)

The comments should provide enough if it is already not clear what is happening. The actual code is very short without comments, and you may have noticed I am not a fan of the semicolon. :)

Commodious

It should be pointed out that this implementation doesn't provide the same performance guarantees as a traditional quicksort -- this uses 2X the amount of array accesses (.filter traverses the whole array) and also does not perform an initial shuffle of the array. – Embarkation

filter, concat, [] and the array destructure also allocate memory, so this is mostly an important contribution to illustrate the high-level operation of quicksort and functional style, but it's slow and isn't stable. Using the first element as the pivot is also not optimal (suggested by the commenter above because shuffling effectively gives random pivots). – Warmonger

Answer 6

var array = [8, 2, 5, 7, 4, 3, 12, 6, 19, 11, 10, 13, 9];
quickSort(array, 0, array.length -1);
document.write(array);


function  quickSort(arr, left, right)
{
	var i = left;
	var j = right;
	var tmp;
	pivotidx = (left + right) / 2; 
	var pivot = parseInt(arr[pivotidx.toFixed()]);  
	/* partition */
	while (i <= j)
	{
		while (parseInt(arr[i]) < pivot)
		i++;
		while (parseInt(arr[j]) > pivot)
			j--;
		if (i <= j)
		{
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			i++;
			j--;
		}
	}

	/* recursion */
	if (left < j)
		quickSort(arr, left, j);
	if (i < right)
		quickSort(arr, i, right);
	return arr;
}

Speciosity

Does the partition function actually work? I found similar code in guru99 and I tried the partition function in python. It didn't quite work. I am posting the python code and the input/ output. – Ftlb

def partition2(array, left, right): pivot = array[math.floor((left + right) / 2)] i = left j = right while i <= j: while array[i] < pivot: i = i+1 while array[j] > pivot: j = j-1 if i <= j: temp = array[j] array[j] = array[i] array[i] = temp j = j-1 i = i+1 return i – Ftlb

Input : [1, 4, 2, 8, 3, 9, 123, 5, 232, 67, 44, 100, 44, 33, 45, 56, 28, 45, 67, 44], output : [1, 4, 2, 8, 3, 9, 44, 5, 67, 45, 44, 28, 44, 33, 45, 56, 100, 67, 232, 123] – Ftlb

Answer 7

In this blog http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/ which has pointed out that Array.sort is implemented in quicksort or merge sort internaly.

Quicksort is generally considered to be efficient and fast and so is used by V8 as the implementation for Array.prototype.sort() on arrays with more than 23 items. For less than 23 items, V8 uses insertion sort[2]. Merge sort is a competitor of quicksort as it is also efficient and fast but has the added benefit of being stable. This is why Mozilla and Safari use it for their implementation of Array.prototype.sort().

and when using Array.sort,you should return -1 0 1 instead of true or false in Chrome.

arr.sort(function(a,b){
  return a<b;
});
// maybe--> [21, 0, 3, 11, 4, 5, 6, 7, 8, 9, 10, 1, 2, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22]
arr.sort(function(a,b){
  return a > b ? -1 : a < b ? 1 : 0;
});
// --> [22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Bruges

returning b-a or a-b is even faster, since Array.sort use a compare to 0 then the only the sign of the returned value (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…) . – Ankh

As of now, Timsort is used in Chrome's V8 engine – Warmonger

Answer 8

Using ES6 rest, spread:

smaller = (a, list) => list.filter(x => x <= a)
larger = (a, list) => list.filter(x => x > a)
qsort = ([x, ...list]) => (!isNaN(x))
    ? [...qsort(smaller(x, list)), x, ...qsort(larger(x, list))]
    : []

Threecornered

Answer 9

This algorithm work almost as fast as the default implementation of Array.prototype.sort in chrome.

function quickSort(t){
    _quickSort(t,0,t.length-1,0,t.length-1);
}

function _quickSort(t, s, e, sp, ep){   
    if( s>=e )  return;
    while( sp<ep && t[sp]<t[e] ) sp++;  
    if( sp==e )
        _quickSort(t,s,e-1,s,e-1);  
    else{
        while(t[ep]>=t[e] && sp<ep ) ep--;      
        if( sp==ep ){
            var temp = t[sp];
            t[sp] = t[e];
            t[e] = temp;
            if( s!=sp ){
                _quickSort(t,s,sp-1,s,sp-1);
            }
            _quickSort(t,sp+1,e,sp+1,e);            
        }else{
            var temp = t[sp];
            t[sp] = t[ep];
            t[ep] = temp;
            _quickSort(t,s,e,sp+1,ep);
        }
    }
}

quickSort time (ms): 738
javaScriptSort time (ms): 603

var m = randTxT(5000,500,-1000,1000);
VS(m);

function VS(M){
    var t;
    t = Date.now();
    for(var i=0;i<M.length;i++){
        quickSort(M[i].slice());
    }console.log("quickSort time (ms): "+(Date.now()-t));

    t = Date.now();
    for(var i=0;i<M.length;i++){
        M[i].slice().sort(compare);
    }console.log("javaScriptSort time (ms): "+(Date.now()-t));
}

function compare(a, b) {
    if( a<b )
        return -1;
    if( a==b )
        return 0;
    return 1;
}

function randT(n,min,max){
    var res = [], i=0;
    while( i<n ){
        res.push( Math.floor(Math.random()*(max-min+1)+min) );
        i++;
    }
    return res; 
}
function randTxT(n,m,min,max){
    var res = [], i=0;
    while( i<n ){
        res.push( randT(m,min,max) );
        i++;
    }
    return res; 
}

Horripilation

Answer 10

Yet another quick sort demonstration, which takes middle of the array as pivot for no specific reason.

const QuickSort = function (A, start, end) {
    // 
    if (start >= end) {
        return;
    }
    // return index of the pivot
    var pIndex = Partition(A, start, end);
    // partition left side
    QuickSort(A, start, pIndex - 1);
    // partition right side
    QuickSort(A, pIndex + 1, end);
}

const Partition = function (A, start, end) {
    if (A.length > 1 == false) {
        return 0;
    }
    let pivotIndex = Math.ceil((start + end) / 2);
    let pivotValue = A[pivotIndex];
    for (var i = 0; i < A.length; i++) {
        var leftValue = A[i];
        // 
        if (i < pivotIndex) {
            if (leftValue > pivotValue) {
                A[pivotIndex] = leftValue;
                A[i] = pivotValue;
                pivotIndex = i;
            }
        }
        else if (i > pivotIndex) {
            if (leftValue < pivotValue) {
                A[pivotIndex] = leftValue;
                A[i] = pivotValue;
                pivotIndex = i;
            }
        }
    }
    return pivotIndex;

}

const QuickSortTest = function () {
    const arrTest = [3, 5, 6, 22, 7, 1, 8, 9];
    QuickSort(arrTest, 0, arrTest.length - 1);
    console.log("arrTest", arrTest);
}
// 
QuickSortTest();

Cordite

Answer 11

I found the normal search mode and wrote:

let QuickSort = (arr, low, high) => {
    if (low < high) {
        p = Partition(arr, low, high);
        QuickSort(arr, low, p - 1);
        QuickSort(arr, p + 1, high);
    }
    return arr.A;
}

let Partition = (arr, low, high) => {
    let pivot = arr.A[high];
    let i = low;
    for (let j = low; j <= high; j++) {
        if (arr.A[j] < pivot) {
            [arr.A[i], arr.A[j]] = [arr.A[j], arr.A[i]];
            i++;
        }
    }
    [arr.A[i], arr.A[high]] = [arr.A[high], arr.A[i]];
    return i;
}

let arr = { A/* POINTER */: [33, 22, 88, 23, 45, 0, 44, 11] };
let res = QuickSort(arr, 0, arr.A.length - 1);
console.log(res);

Result is [0, 11, 22, 23, 33, 44, 45, 88] But its not stable; so I checked the other answers and the Idea of @6502 was interesting to me that "two items do not have to be the same" to be distinguishable. Well, I have a solution in my mind, but it is not optimal. We can keep the indexes of the items in a separate array. Memory consumption will almost double in this idea.

arr.A => Array of numbers

arr.I => Indexes related to each item of A

influencer => This should be a very very small number; I want to use this as a factor to be able to distinguish between similar items.

So we can change the partition like this:

let Partition = (arr, low, high) => {
    let pivot = arr.A[high];
    let index = arr.I[high];
    let i = low;
    for (let j = low; j <= high; j++) {
        if (arr.A[j] + (arr.I[j] * influencer) < pivot + (index * influencer)) {
            [arr.A[i], arr.A[j]] = [arr.A[j], arr.A[i]];
            [arr.I[i], arr.I[j]] = [arr.I[j], arr.I[i]];
            i++;
        }
    }
    [arr.A[i], arr.A[high]] = [arr.A[high], arr.A[i]];
    [arr.I[i], arr.I[high]] = [arr.I[high], arr.I[i]];
    return i;
}

let influencer = 0.0000001;

let arr = {
    I/* INDEXES */: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
    A/* POINTER */: [33, 22, 88, 33, 23, 45, 33, 89, 44, 11]
};
let res = QuickSort(arr, 0, arr.A.length - 1);
console.log(res);

Result:

I: [19, 11, 14, 10, 13, 16, 18, 15, 12, 17],
A: [11, 22, 23, 33, 33, 33, 44, 45, 88, 89]

Periscope

Answer 12

try my solution

const quickSort = (arr) => {

    // base case
    if(arr.length < 2) return arr;

    // recurisve case

    // pick a random pivot
    let pivotIndex = Math.floor(Math.random() * arr.length);
    let pivot = arr[pivotIndex];
    let left = [];
    let right = [];

    // make  array of the elements less than pivot and greater than it
    for(let i = 0; i < arr.length; i++) {
        if(i === pivotIndex) {
            continue;
        }

        if(arr[i] < pivot) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    
    // call the recursive case again
    return quickSort(left).concat([pivot], quickSort(right));
} 

when testing this

quickSort([7, 5, 3, 2, 8, 1, 5])   // returns [[1, 2, 3, 5, 5, 7, 8]]

Snavely

Answer 13

More compact and easy to understand quicksort implementation

const quicksort = arr =>
  arr.length <= 1
    ? arr
    : [
        ...quicksort(arr.slice(1).filter((el) => el < arr[0])),
        arr[0],
        ...quicksort(arr.slice(1).filter((el) => el >= arr[0])),
      ];

Grundy

Welcome to Stack Overflow. Code dumps without any explanation are rarely helpful. Stack Overflow is about learning, not providing snippets to blindly copy and paste. Please edit your question and explain how it answers the specific question being asked. See How to Answer. Note also that this question is over 10 years old and has 17 existing answers. In such cases it is especially important to explain how your answer improves over what is already there. – Kaleykaleyard

Answer 14

Quicksort using ES6, filter and spread operation.

We establish a base case that 0 or 1 elements in an array are already sorted. Then we establish an inductive case that if quicksort works for 0 or 1 elements, it can work for an array of size 2. We then divide and conquer until and recursively call our function until we reach our base case in the call stack to get our desired result.

O(n log n)

const quick_sort = array => {
  if (array.length < 2) return array; // base case: arrays with 0 or 1 elements are already "sorted"
  const pivot = array[0]; // recursive case;
  const slicedArr = array.slice(1); 
  const left = slicedArr.filter(val => val <= pivot); // sub array of all elements less than pivot
  const right = slicedArr.filter(val => val > pivot); // sub array of all elements greater than pivot
  return [...quick_sort(left), pivot, ...quick_sort(right)];
 }

Nutria

Answer 15

const quicksort = (arr)=>{

  const length = Math.ceil(arr.length/2);
  const pivot = arr[length];
  let newcondition=false;
  for(i=0;i<length;i++){
    if(arr[i]>arr[i+1]){  
      [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      newcondition =true
    }
  }
  
  for(i=arr.length;i>length-1;i--){
     if(arr[i]>arr[i+1]){
      [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      newcondition =true
    }
  }
  return newcondition? quicksort(arr) :arr
 
}
const t1 = performance.now()
quicksort([3, 2, 4, 9, 1, 0, 8, 7])
const t2 = performance.now()
console.log(t2-t1)

const quicksort = (arr)=>{

  const length = Math.ceil(arr.length/2);
  const pivot = arr[length];
  let newcondition=false;
  for(i=0;i<length;i++){
    if(arr[i]>arr[i+1]){  
      [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      newcondition =true
    }
  }
  
  for(i=arr.length;i>length-1;i--){
     if(arr[i]>arr[i+1]){
      [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      newcondition =true
    }
  }
  return newcondition? quicksort(arr) :arr
 
}

console.log(quicksort([3, 2, 4, 9, 1, 0, 8, 7]))

Dichroite

Answer 16

TypeScript version. O(nlogn)

type NumArr = Array<number>;
function quikSort(arr: NumArr): NumArr {
  if (arr.length < 2) {
    return arr;
  }
  const anchorIndex: number = Math.floor((arr.length - 1) / 2);
  const anchor: number = arr[anchorIndex];
  const greater: NumArr = [];
  const lesser: NumArr = [];
  anchor
  for (let index = 0; index < arr.length; index++) {
    const element = arr[index];
    if (element !== anchor) {
      if (element > anchor) {
        greater.push(element);
      } else {
        lesser.push(element);
      }
    }
  }
  return [...quikSort(lesser), anchor, ...quikSort(greater)];
}
const arrNum: NumArr = [2, 8, 1, 0, 25];
const answer: NumArr = quikSort(arrNum);

In anchorIndex value, you can also use Math.random(). But i like always take middle as an index.

Garver

Answer 17

This is it !!!

function typeCheck(a, b){
  if(typeof a === typeof b){
    return true;
  }else{
    return false;
  }
}

function qSort(arr){
  if(arr.length === 0){
    return [];
  }

  var leftArr = [];
  var rightArr = [];
  var pivot = arr[0];

  for(var i = 1; i < arr.length; i++){
    if(typeCheck(arr[i], parseInt(0))){
      if(arr[i] < pivot){
        leftArr.push(arr[i]);
      }else { rightArr.push(arr[i]) } 
    }else{
      throw new Error("All must be integers");
    }
  }

  return qSort(leftArr).concat(pivot, qSort(rightArr));

}

var test = [];

for(var i = 0; i < 10; i++){
  test[i] = Math.floor(Math.random() * 100 + 2);
}

console.log(test);
console.log(qSort(test));

Polston

This is what? Please explain your code. – Technicolor

Answer 18

Slim version:

function swap(arr,a,b){
    let temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp
    return 1
}

function qS(arr, first, last){
    if(first > last) return

    let p = first
    for(let i = p; i < last; i++)
        if(arr[i] < arr[last]) 
            p += swap(arr, i, p)

    swap(arr, p, last)

    qS(arr, first, p - 1)
    qS(arr, p + 1, last)
}

Tested with random values Arrays, and seems to be always faster than Array.sort()

Limiter

This is not a stable sort. en.wikipedia.org/wiki/Sorting_algorithm#Stability – Agitate

Answer 19

quickSort = (array, left, right) => {
    if (left >= right) {
        return;
    }
    const pivot = array[Math.trunc((left + right) / 2)];
    const index = partition(array, left, right, pivot);
    quickSort(array, left, index - 1);
    quickSort(array, index, right);
}

partition = (array, left, right, pivot) => {
    while (left <= right) {
        while (array[left] < pivot) {
            left++;
        }
        while (array[right] > pivot) {
            right--;
        }
        if (left <= right) {
            swap(array, left, right);
            left++;
            right--;
        }
    }
    return left;
}

swap = (array, left, right) => {
    let temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}
let array = [1, 5, 2, 3, 5, 766, 64, 7678, 21, 567];
quickSort(array, 0, array.length - 1);
console.log('final Array: ', array);

Adelbert

This is not a stable sort. en.wikipedia.org/wiki/Sorting_algorithm#Stability – Agitate

Answer 20

const quickSort = array =>
  (function qsort(arr, start, end) {
    if (start >= end) return arr;
    let swapPos = start;

    for (let i = start; i <= end; i++) {
      if (arr[i] <= arr[end]) {
        [arr[swapPos], arr[i]] = [arr[i], arr[swapPos]];
        swapPos++;
      }
    }
    qsort(arr, start, --swapPos - 1);
    qsort(arr, swapPos + 1, end);

    return arr;
  })(Array.from(array), 0, array.length - 1);

Grundy

Please explain your code. Undescribed code blocks are seldom helpful to readers. – Technicolor

Answer 21

const quicksort = (arr)=>{

  const length = Math.ceil(arr.length/2);
  const pivot = arr[length];
  let newcondition=false;
  for(i=0;i<length;i++){
    if(arr[i]>arr[i+1]){  
      [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      newcondition =true
    }
  }
  
  for(i=arr.length;i>length-1;i--){
     if(arr[i]>arr[i+1]){
      [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      newcondition =true
    }
  }
  return newcondition? quicksort(arr) :arr
 
}
const t1 = performance.now();
const t2 = performance.now();
console.log(t2-t1);
console.log(quicksort([3, 2, 4, 9, 1, 0, 8, 7]));

Dichroite

Please explain your code. Undescribed code blocks are seldom helpful to readers – Technicolor

Answer 22

const quicksort = (arr)=>{
  if (arr.length < 2) return arr;
  const pivot = arr[0];
  const left = [];
  const right = [];
  arr.shift();   
  arr.forEach(number => {
    (number<pivot) ? left.push(number) : right.push(number);
  });
 return ([...quicksort(left), pivot, ...quicksort(right)]);
}
console.log(quicksort([6, 23, 29, 4, 12, 3, 0, 97]));

Dichroite

Please explain your code. Undescribed code blocks are seldom helpful to readers – Technicolor

Answer 23

How about this non-mutating functional QuickSort:

const quicksort = (arr, comp, iArr = arr) => {
  if (arr.length < 2) {
    return arr;
  }
  const isInitial = arr.length === iArr.length;
  const arrIndexes = isInitial ? Object.keys(arr) : arr;
  const compF = typeof comp === 'function'
  ? comp : (left, right) => left < right ? -1 : right < left ? 1 : 0;
  const [pivotIndex, ...indexesSansPivot] = arrIndexes;
  const indexSortReducer = isLeftOfPivot => [
    (acc, index) => isLeftOfPivot === (compF(iArr[index], iArr[pivotIndex]) === -1)
    ? acc.concat(index) : acc,
    []
  ];
  const ret = quicksort(indexesSansPivot.reduce(...indexSortReducer(true)), compF, iArr)
  .concat(pivotIndex)
  .concat(quicksort(indexesSansPivot.reduce(...indexSortReducer(false)), compF, iArr));
  return isInitial ? ret.reduce((acc, index) => acc.concat([arr[index]]), []) : ret;
};

As a bonus, it supports optional comparing function which enables sorting of array of objects per property/properties, and doesn't get slower if dealing with larger values/objects.

First quick sorts original array keys, then returns sorted copy of original array.

Caracalla