StoogeSort.js

/*
 * 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
}