gistfile1.js

var assert = require('assert')

function Node(){
  this.parent
  this.data
  this.next
  this.index
}

function sort(a, index, p){
  if(index === a.length+1){
    return a
  }
  if(a.length === 0) return []
  if(typeof index === 'undefined') index = a.length-1
  if(index<0){
    return traversal(a)
  }
  if(index === a.length-1){
    var node = new Node
    node.parent = null
    node.data = a[index]
    node.index = index
    node.next = null
    a[index] = node
    return sort(a, index-1, index)
  }else{
    if(a[index] === a[p].data){
      var node = new Node
      node.parent = p
      node.data = a[index]
      node.index = index
      node.next = a[p].next
      a[index] = node
      a[p].next = index
      if(a[index].next !== null) a[a[index].next].parent = index
      return sort(a, index-1, index)
    }else if(a[index] > a[p].data){
      if(a[p].parent === null){
        var node = new Node
        node.parent = null
        node.data = a[index]
        node.index = index
        node.next = p
        a[index] = node
        a[p].parent = index
        return sort(a, index-1, index)
      }else if(a[index] > a[p].data && a[index] < a[a[p].parent].data){
        var node = new Node
        node.parent = a[p].parent
        node.data = a[index]
        node.index = index
        node.next = a[p].index
        a[index] = node
        a[p].parent = index
        a[a[index].parent].next = index
        return sort(a, index-1, index)
      }else return sort(a, index, a[p].parent)
    }else{
      if(a[p].next === null){
        var node = new Node
        node.parent = p
        node.data = a[index]
        node.index = index
        node.next = null
        a[p].next = index
        a[index] = node
        return sort(a, index-1, index)
      }else return sort(a, index, a[p].next)
    }
  }
}

function traversal(a, index, res){
  if(typeof index === 'undefined') index = a.length-1
  if(a[index].next === null){
    if(print(a, index)) return print(a, index)
  }else return traversal(a, a[index].next)
}

function print(a, index, res){
  if(!res){
    res = []
    res[0] = a[index].data
    return print(a, a[index].parent, res)
  }else{
    if(index === null){
      return sort(res, res.length+1)
    }else{
      res[res.length] = a[index].data
      return print(a, a[index].parent, res)
    }
  }
}



function arrayEqual(arrayA, arrayB) {
  if(arrayA.length!=arrayB.length) return false
 
  for(var i=0; i<arrayA.length; ++i) {
    if(arrayA[i]!=arrayB[i])
      return false
  }
 
  return true
}
 
assert(arrayEqual(sort([]), []))
assert(arrayEqual(sort([1]), [1]))
assert(arrayEqual(sort([1, 1]), [1, 1]))
assert(arrayEqual(sort([1, 2]), [1, 2]))
assert(arrayEqual(sort([1, 2, 3]), [1, 2, 3]))
assert(arrayEqual(sort([3, 2, 1]), [1, 2, 3]))
assert(arrayEqual(sort([3, 1, 2]), [1, 2, 3]))
assert(arrayEqual(sort([1, 3, 2]), [1, 2, 3]))
assert(arrayEqual(sort([5, 3, 2, 6, 8, 9, 4, 3 ,5, 1]), [1, 2, 3, 3, 4, 5, 5, 6, 8, 9]))