I try to implement a sorting algorithm that works as follows: given an array of length n the algorithm should recursively call itself on the first 2/3, then on the last 2/3 and after that again on the first 2/3 of the array. On each call the algorithm should sort the current array when it is looking at two or less elements and exit. The method should take an array A and two indices as arguments.
So the main difficulty here is to create indices that represent the 2/3 of an array. My idea was to do x = Math.floor((i-j)/3) such that x is the number of elements in the first 1/3 and in the second 1/3. So the first 2/3 can be bounded by [i,x*2] and the last 2/3 by [x+1,j]. Do you see any mistakes in this idea?
I came up with following algorithm which is not working correctly. I get an error:
RangeError: Maximum call stack size exceeded
So either the algorithm or the idea above are flawed. Do you see any problems?
var threeSort = function(A,i,j) {
var diff = j-i;
if (diff <= 2) {
if (A[j] < A[i]) {
var tmp = A[i];
A[i] = A[j];
A[j] = tmp;
retu;
}
}
var x = Math.floor(diff/3);
threeSort(A,i,x*2);
threeSort(A,x+1,j);
threeSort(A,i,x*2);
};
var arr = [3,4,1,4,2];
threeSort(arr, 0, arr.length-1);
