# Not sure how test 4 can pass but 2 does not

Tell us what’s happening:
Tried to implement it without using for loops. As far as I can tell the output is correct.

``````  **Your code so far**
``````
``````
function insertionSort(array) {
// Only change code below this line
if (array.length < 1 ) {return array;}

let sortInto = (sorted, unsorted)=> {
if (unsorted.length < 1) {return sorted;}

let toBeInserted = unsorted.shift();

let  insert = (sortedArray = [], element) => {
if(sortedArray.length < 1) {return [element]}
else{

if (element > sortedArray[sortedArray.length-1]){
return [...sortedArray, element];
} else{
unsorted.unshift(sortedArray.pop());
return insert(sortedArray, element);
}
}
}
let sort = insert(sorted, toBeInserted);
return sortInto(sort, unsorted)
}

return sortInto([], array);

// Only change code above this line
}
``````
``````  **Your browser information:**
``````

User Agent is: `Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/97.0.4692.99 Safari/537.36`

Challenge: Implement Insertion Sort

By using this sort of recursion-esk approach, you are just obfuscating the fact that you are using while loop logic and making your debugging harder.

When I test your code, I get `InternalError: too much recursion`, so I suspect you are not correctly reaching your base case.

In functional programming we try not to use while loops. In languages that support TCO it would be advantages for memory use - not sure there is any advantage in javascript - also I sort of broke FP rules in accessing the unsorted array in the insert lamda so I can’t claim pure FP here. This worked on my system the only change I made was puting the sortInto lamda inside the insertionSort function since the tester didn’t seem to want me to call methods outside of it. Which I think should work but I’ll admit I didn’t try first.

I’m aware that some people religiously avoid while loops, but this does mean that you have decided to make your code more difficult to write and debug. Recursion isn’t especially efficient in Javascript and should be reserved for times when it is the clearest way to write the solution, which is rare.

When I run

your code with the bigger test case
``````function insertionSort(array) {
// Only change code below this line
if (array.length < 1) {
return array;
}

const sortInto = (sorted, unsorted) => {
if (unsorted.length < 1) {
return sorted;
}

const toBeInserted = unsorted.shift();
const insert = (sortedArray = [], element) => {
if (sortedArray.length < 1) {
return [element];
} else {
if (element > sortedArray[sortedArray.length - 1]) {
return [...sortedArray, element];
} else {
unsorted.unshift(sortedArray.pop());
return insert(sortedArray, element);
}
}
}
const sort = insert(sorted, toBeInserted);
return sortInto(sort, unsorted)
}

return sortInto([], array);
// Only change code above this line
}

console.log(insertionSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]));
``````

I get the error `InternalError: too much recursion`, so you either never reach your base case or you are reaching it so slowly that my browser loses confidence in your code and stops adding function calls to the stack.

1 Like

Yeah I’m clearly not understanding something. This is the version I had working on my system. trying it with largest test case now.

``````let insertionSorted = (toBeSorted) => {
return sortInto([], toBeSorted);
}

let sortInto = (sorted, unsorted)=> {
if (unsorted.length < 1) {return sorted;}

let toBeInserted = unsorted.shift();

let  insert = (sortedArray = [], element) => {
if(sortedArray.length < 1) {return [element]}
else{

if (element > sortedArray[sortedArray.length-1]){
return [...sortedArray, element];
} else{
unsorted.unshift(sortedArray.pop());
return insert(sortedArray, element);
}
}
}
let sort = insert(sorted, toBeInserted);
return sortInto(sort, unsorted)
}

//let myArray = [23,5,2];
let myArray = [8,4,2,3];
console.log(insertionSorted(myArray));
``````

Okay yeah I see now it’s a size of the stack issue so no good with large arrays. Thanks.

1 Like

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.