Responsive Ad Area

Share This Post

test

Recursive sort in JS

I was asked in an interview to write a program/algo to sort an array of number using recursion.

Though I vaguely answered it, I tried and came up with following code:

You can use following JSFiddle link to play around.

function sort(arr) {
	if (arr.length === 2) {
  	const v1 = arr[0];
    const v2 = arr[1];
    const isGreater = (
    	(isString(v1) && isString(v2) && v1.toString().toLocaleCompare(v2) > 0) ||
      (isNumber(v1) && isNumber(v2) && v1 > v2)
    );
  	return isGreater ? [ v2, v1 ] : [ v1, v2 ];
  } else {
  	const last = arr.pop();
    const ret = sort(arr);
    const newLast = ret.peekLast();
    
    if (newLast < last) {
      return [ ...ret, last ];
    } else {
    	return sort( [ last, ...ret ] );
    }
  }
}

function isString(value) { return typeof value === 'string'; }
function isNumber(value) { return Number.isFinite(value); }
Array.prototype.peekLast = function () { return this.slice().pop(); }

//console.log(sort([1,2,3,4,5]))

console.log(sort([5,4,3,2,1]))

The algo I implemented is:

  • Take the array and check if its length is greater than 2.
  • If yes,
    • Remove last element and store it in a variable.
    • Again call same function without last element till it has 2 items.
    • Accept array returned from recursive call and peek the last element.
    • If newLast value is greater than previousLast
      • Push previousLast as first element and again call itself with this array.
    • If not, push previousLast to array and return it.
  • Else,
    • For number and string check equality and return correct order.
    • For anything else, return same value

Question is, is there a better way to implement (algo wise)?

Note: I’m not expecting code improvements. Objective of this question is improvement in algo part or any general stuff I have missed.

I also know, current code does not support:

  • Sort order. It will sort ascending only.
  • May break for Date objects, and does not support Objects in general.

Thanks!


Recursive sort in JS
Recursive sort in JS
test
{$excerpt:n}

Share This Post

Leave a Reply

Your email address will not be Publishedd. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Skip to toolbar