arraySorts.js

var defCompare = function(a, b) {
 var aStr = String(a),
     bStr = String(b);
    
  if (aStr > bStr) {
    return 1;
  }
  else if (aStr < bStr) {
    return -1;
  }
  else {
    return 0;
  }
}

var arraySortOneBubbleSortPass = function(vs, comparator) {
  if(comparator == null) {
    comparator = defCompare
  }
  else {
    
  }

  if(vs.length < 2) {
    //# array too small
    return vs
  }
  else if(vs.length == 2) {
    //# just one pair
    if(comparator(vs[0], vs[1]) > 0) {
      var temp = vs[0]; vs[0] = vs[1]; vs[1] = temp
    }
    else {
      
    }
    return vs
  }
  else {
    //# general case
    //# one pass compare and swap 
    var swapsCount = 0
    for(var i = 0; i != vs.length; i += 1) {
      if(comparator(vs[i + 0], vs[i + 1]) > 0) {
        swapsCount += 1
        var temp = vs[i + 0]; vs[i + 0] = vs[i + 1]; vs[i + 1] = temp
      }
      else {
      }
    }
  
    //# no swaps - already sorted
    if(swapsCount == 0) {
      return vs
    }
    else {
      //# at least one element bubbled up and already at right place
      var last = vs.pop()
      //# but rest still unsorted
      vs.sort()
      vs.push(last)
      return vs
    }
  }
}

var arraySortFindUnsortedBlockEdges = function(vs, comparator) {
  if(comparator == null) {
    comparator = defCompare
  }
  else {
    
  }

  if(vs.length < 2) {
    //# array too small
    return vs
  }
  else if(vs.length == 2) {
    //# just one pair
    if(comparator(vs[0], vs[1]) > 0) {
      var temp = vs[0]; vs[0] = vs[1]; vs[1] = temp
    }
    else {
      
    }
    return vs
  }
  else {
    //# general case
    
    //# run forward and find 1st unsorted pair key
    var firstUnsortedPairKey = 0
    for(;;) {
      if(comparator(vs[firstUnsortedPairKey], vs[firstUnsortedPairKey + 1]) > 0) {
        break
      }
      else {
        firstUnsortedPairKey += 1
        if(firstUnsortedPairKey == vs.length) {
          break
        }
        else {
          
        }
      }
    }
    
    //# no unsorted pairs - already sorted
    if(firstUnsortedPairKey == vs.length) {
      return vs
    }
    else {
      //# run backward and find last unsorted pair key
      var lastUnsortedPairKey = vs.length - 2
      for(;;) {
        if(comparator(vs[lastUnsortedPairKey], vs[lastUnsortedPairKey + 1]) > 0) {
          break
        }
        else {
          lastUnsortedPairKey -= 1
          if(lastUnsortedPairKey == -1) {
            break
          }
          else {
            
          }
        }
      }
      
      //# sort middle and concat w/ already sorted parts
      return [].concat(
        vs.slice(0, firstUnsortedPairKey), 
        vs.slice(firstUnsortedPairKey, lastUnsortedPairKey + 2).sort(comparator), 
        vs.slice(lastUnsortedPairKey + 2, vs.length)
      )
    }
  }  
}

console.assert(String(arraySortOneBubbleSortPass([])) == String([]))
console.assert(String(arraySortOneBubbleSortPass([1])) == String([1]))
console.assert(String(arraySortOneBubbleSortPass([1, 2])) == String([1, 2]))
console.assert(String(arraySortOneBubbleSortPass([2, 1])) == String([1, 2]))
console.assert(String(arraySortOneBubbleSortPass([3, 2, 1])) == String([1, 2, 3]))
console.assert(String(arraySortOneBubbleSortPass([5, 3, 4, 2, 1])) == String([1, 2, 3, 4, 5]))

console.assert(String(arraySortFindUnsortedBlockEdges([])) == String([]))
console.assert(String(arraySortFindUnsortedBlockEdges([1])) == String([1]))
console.assert(String(arraySortFindUnsortedBlockEdges([1, 2])) == String([1, 2]))
console.assert(String(arraySortFindUnsortedBlockEdges([2, 1])) == String([1, 2]))
console.assert(String(arraySortFindUnsortedBlockEdges([3, 2, 1])) == String([1, 2, 3]))
console.assert(String(arraySortFindUnsortedBlockEdges([5, 3, 4, 2, 1])) == String([1, 2, 3, 4, 5]))