/*
 * Stooge Sort sorts an array based on divide and conquer principle
 * note the exceptionally bad time complexity
 * more information: https://en.wikipedia.org/wiki/Stooge_sort
 *
 */
export function stoogeSort(items, leftEnd, rightEnd) {
  if (items[rightEnd - 1] < items[leftEnd]) {
    const temp = items[leftEnd]
    items[leftEnd] = items[rightEnd - 1]
    items[rightEnd - 1] = temp
  }
  const length = rightEnd - leftEnd
  if (length > 2) {
    const third = Math.floor(length / 3)
    stoogeSort(items, leftEnd, rightEnd - third)
    stoogeSort(items, leftEnd + third, rightEnd)
    stoogeSort(items, leftEnd, rightEnd - third)
  }
  return items
}