JavaScript Program for Quick Sort Algorithm

A quick sort in JavaScript can be done using a function like function quickSort(arr) { if (arr.length <= 1) return arr; const pivot = arr[arr.length - 1]; const left = arr.filter(x => x < pivot); const right = arr.filter(x => x > pivot); const middle = arr.filter(x => x === pivot); return [...quickSort(left), ...middle, ...quickSort(right)]; } which sorts an array by dividing it around a pivot.

Examples

Input[3, 1, 4, 1, 5]

Output[1,1,3,4,5]

Input[10, 7, 8, 9, 1, 5]

Output[1,5,7,8,9,10]

Input[]

Output[]

How to Think About It

To sort an array quickly, pick one element as a pivot. Then split the array into two parts: one with elements smaller than the pivot and one with elements bigger. Sort these parts by repeating the same steps, then join them back with the pivot in the middle.

Algorithm

1

Check if the array has 1 or no elements; if yes, return it as sorted.

2

Choose the last element as the pivot.

3

Create three new arrays: one for elements less than the pivot, one for elements equal to the pivot, and one for elements greater.

4

Recursively apply quick sort to the less and greater arrays.

5

Combine the sorted less array, equal elements, and sorted greater array into one sorted array.

6

Return the combined sorted array.

Code

javascript

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[arr.length - 1];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

console.log(quickSort([3, 1, 4, 1, 5]));

Output

[1,1,3,4,5]

Dry Run

Let's trace quickSort([3, 1, 4, 1, 5]) through the code

1

Initial call

Array: [3, 1, 4, 1, 5], pivot = 5

2

Split into left, middle, and right

left = [3, 1, 4, 1], middle = [5], right = []

3

Recursive call on left

quickSort([3, 1, 4, 1])

4

Pivot in left call

pivot = 1, left = [], middle = [1,1], right = [3, 4]

5

Recursive calls on left and right of left

quickSort([]) returns [], quickSort([3,4]) continues

6

Pivot in right of left call

pivot = 4, left = [3], middle = [4], right = []

7

Recursive calls on [3] and []

quickSort([3]) returns [3], quickSort([]) returns []

8

Combine right of left

[3,4]

9

Combine left call

[1,1,3,4]

10

Combine all

[1,1,3,4,5]

Call	Array	Pivot	Left	Middle	Right	Result
1	[3,1,4,1,5]	5	[3,1,4,1]	[5]	[]	[1,1,3,4,5]
2	[3,1,4,1]	1	[]	[1,1]	[3,4]	[1,1,3,4]
3	[3,4]	4	[3]	[4]	[]	[3,4]
4	[3]	3	[]	[3]	[]	[3]
5	[]	-	-	-	-	[]

Why This Works

Step 1: Choosing a pivot

The pivot divides the array into smaller, equal, and bigger parts, helping to sort by comparison.

Step 2: Splitting the array

Elements less than pivot go left, equal elements go to middle, and greater go right, so sorting happens in smaller groups.

Step 3: Recursion

Sorting left and right parts by calling quickSort again breaks the problem into simpler pieces.

Step 4: Combining results

Joining sorted left, middle, and sorted right gives the fully sorted array.

Alternative Approaches

In-place Quick Sort

javascript

function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  let pivot = arr[right];
  let i = left;
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];
  quickSortInPlace(arr, left, i - 1);
  quickSortInPlace(arr, i + 1, right);
}

const arr = [3,1,4,1,5];
quickSortInPlace(arr);
console.log(arr);

This version sorts the array without extra space but is more complex to understand.

Quick Sort with Middle Pivot

javascript

function quickSortMiddlePivot(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
  return [...quickSortMiddlePivot(left), ...middle, ...quickSortMiddlePivot(right)];
}

console.log(quickSortMiddlePivot([3,1,4,1,5]));

Choosing the middle element as pivot can reduce worst-case scenarios but requires handling equal elements.

Complexity: O(n log n) average, O(n^2) worst time, O(n) space

Time Complexity

Quick sort divides the array and sorts parts recursively, leading to average O(n log n) time. Worst case is O(n^2) when pivot choices are poor.

Space Complexity

This implementation uses extra arrays for left, middle, and right, so space is O(n). In-place versions use O(log n) space.

Which Approach is Fastest?

In-place quick sort is faster and uses less memory but is harder to implement. The simple filter-based method is easier to understand.

Approach	Time	Space	Best For
Filter-based Quick Sort	O(n log n) avg, O(n^2) worst	O(n)	Learning and clarity
In-place Quick Sort	O(n log n) avg, O(n^2) worst	O(log n)	Performance and memory efficiency
Middle Pivot Quick Sort	O(n log n) avg, better worst case	O(n)	Reducing worst-case scenarios