Quick Sort

Hint

Select a middle element as pivot from the list. Do a partition to create three empty sublists: left, pivot, and right. Go through each item in the list:

• If the item is less than the pivot, add it to the left sublist.
• If the item is equal to the pivot, add it to the pivot sublist.
• If the item is greater than the pivot, add it to the right sublist.

Apply the same steps (choose a pivot, partition) to the left and right sublists. When a sublist has only one item or is empty, it's already sorted. Concatenate the sorted left sublist, the pivot sublist, and the sorted right sublist to get the final sorted list.

• Python
• Javascript
•  Run

def sort(ls):
  if len(ls) <= 1:
    return ls
  
  middle = ls[len(ls) // 2]
  left = []
  pivot = []
  right = []

  for i  in range(len(ls)):
    item = ls[i]
    
    if item < middle:
      left.append(item)
    
    if item == middle:
      pivot.append(item)
    
    if item > middle:
      right.append(item)

  return sort(left) + pivot + sort(right)

ls = [1, 2, 8, 9, 5, 7, 6, 4, 3]

print(sort(ls))

function sort(list) {
  if (list.length <= 1) {
    return list;
  }

  const middle = list[Math.round(list.length / 2)];
  const left = [];
  const pivot = [];
  const right = [];

  for (let i = 0; i < list.length; i++) {
    let item = list[i];
    
    if (item < middle) {
      left.push(item);
    }
    
    if (item == middle) {
      pivot.push(item);
    }
    
    if (item > middle) {
      right.push(item);
    }
  }

  return [...sort(left), ...pivot, ...sort(right)];
}

const data = [1, 2, 8, 9, 5, 7, 6, 4, 3];

console.log(sort(data));