Sort array

Given an array of integers arr, sort the array without using any built-in functions.

Hint

Try quick sort. 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

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

def sort(ls):
  if len(ls) <= 0:
    return ls
  
  m = ls[len(ls) // 2]
  l = []
  p = []
  r = []

  for item in ls:
    if item < m:
      l.append(item)
    elif item == m:
      p.append(item)
    else:
      r.append(item)

  return sort(l) + p + sort(r)

print(sort(ls))

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

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

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

  for (let item of list) {
    if (item < middle) {
      left.push(item);
    }
    
    if (item == middle) {
      pivot.push(item);
    }
    
    if (item > middle) {
      right.push(item);
    }
  }
  
  return [...sort(left), ...pivot, ...sort(right)];
}

console.log(sort(list));