function recursiveInsertionSort(list) {
// insert subroutine,
// inserts nth elelement in sorted lst[0...n-1] list
function insert(lst, n) {
var key = lst[n];
var i = n - 1;
while (i >= 0 && lst[i] > key) {
lst[i + 1] = lst[i];
i = i - 1;
}
lst[i + 1] = key;
}
// the main recursive sort routine
function sort(lst, n) {
if (n > 0) {
sort(lst, n - 1);
insert(lst, n);
}
return lst;
}
// do the sorting
return sort(list, list.length - 1);
}
Problem Statement: Sort a given list of numbers
Solution: We use a recursive variant of insertion sort to solve this problem. the main sort function recursively sorts first n-1 elements and inserts nth element in its proper location using insert routine. Running time of this algorithm can be expressed as T(n) = T(n-1) + O(n) OR, T(n) = O(n²)