Burrows–Wheeler transform

function bwt_encode(str){
    let o=[], cs=str;
    o.push({w: cs, i: 0});
    for(let i=1; i<str.length; i++){
        cs = cs.substring(1, cs.length)+cs[0];
        o.push({w: cs, i: i});
    }
    let s=o.slice();
    s.sort(function(a, b){  return (a.w<=b.w)?-1:1; });
    let index=0, k, res="";
    while( s[index].i!=1 ){ res+=s[index].w[s[index].w.length-1]; index++; }
    k=index;
    while( k<s.length ){ res+=s[k].w[s[k].w.length-1]; k++; }
    return [res, index];
}

function bwt_decode(encoded, index){
    let o=[];
    for(let k=0; k<encoded.length; k++){
        o.push({c: encoded[k], i: k});
    }
    let s=o.slice();
    mergeSort(s, function(a, b){
        return (a.c<=b.c)?-1:1;
    });
    let k=0, res="";
    while(k<encoded.length){
        res+=o[index].c;
        index=s[index].i;
        k++;
    }
    return res;
}


function mergeSort(t, s, e, compare){
    let st, en, comp;
    if( arguments[2]==undefined ){
        st=0; en=t.length-1;
        comp=(arguments[1]==undefined)?function(a, b){  return a-b; }:s;
    }else{
        st=s; en=e;
        comp=(arguments[3]==undefined)?function(a, b){  return a-b; }:compare;
    }
    _mergeSort(t, st, en, comp);
}

function _mergeSort(t, s, e, compare){
    if( s>=e )
        return;
    var isSorted , k=s;
    while( k<e && compare(t[k], t[k+1])==-1/*t[k]<t[k+1]*/ ) k++;
    isSorted = k==e;
    if( !isSorted ){
        var se = Math.floor((s+e)/2);
        _mergeSort(t, s, se, compare);
        _mergeSort(t, se+1, e, compare);
        var c = [], i=s, j=se+1;
        while( i<=se && j<=e ){
            if( compare(t[i], t[j])==-1 ){ c.push(t[i]); i++;
            }else{ c.push(t[j]); j++; }
        }
        while( i<=se ){ c.push(t[i]); i++; }
        while( j<=e ){ c.push(t[j]); j++; }
        j=0;
        for(i=s;i<=e;i++){ t[i] = c[j]; j++; }
    }
}