Алгоритм вставки нескольких столбцов для виртуальной «таблицы»?

Question

У меня есть «таблица» JavaScript, сделанная из массива с «строками», выполненными из объектов, имеющих сходную структуру (свойства элементов похожи на «столбцы» формы с их значениями как «ячейки»).

Таблица сортируется с одним или несколькими столбцами каскадным способом с помощью метода mergesort, применяемого в обратном порядке и может быть от 20 до 20 000 строк в длину.

Каков наилучший алгоритм, используемый для вставки новой строки в таблицу в нужном месте без повторной сортировки всей таблицы (или, скорее, , чтобы найти индекс вставки для новой строки)?

Примером этого может быть:

Sort Order = name, id 

id name description 
0  a  blah 
1  b  foo 
2  d  blah 
3  d  blah 2 
... 
19 d  blah 18 

Insert: 

id name description 
20 c  bar 

To Yield: 

id name description 
0  a  blah 
1  b  foo 
20 c  bar 
2  d  blah 
3  d  blah 2 
... 
19 d  blah 18 

(жаль всех приведенных определений, когда я попытался задать этот вопрос в первый раз, как представляется, много путаницы от людей, верящих «стол "относится к таблице SQL-базы данных или аналогичный)

Answer 1

решили эту проблему следующим образом для тех, кто интересуется:

var table = [ 
    {i: 0, id: 0, id2: 0, id3: 0}, 
    {i: 1, id: 0, id2: 1, id3: 0}, 
    {i: 2, id: 1, id2: 0, id3: 0}, 
    {i: 3, id: 1, id2: 2, id3: 0}, 
    {i: 4, id: 1, id2: 3, id3: 0}, 
    {i: 5, id: 2, id2: 0, id3: 1}, 
    {i: 6, id: 2, id2: 0, id3: 2}, 
    {i: 7, id: 2, id2: 1, id3: 0}, 
    {i: 8, id: 2, id2: 1, id3: 1}, 
    {i: 9, id: 2, id2: 2, id3: 0} 
    ]; 

var sort = ['id', 'id2']; 

function InsertionIndex(table, sort, row) { 
    var state = { 
     _compare: function (left, right) { 
      if (left < right) { return (1); } 
      else if (left > right) { return (-1); } 
      return (0); 
     }, 
     column: '', 
     max: table.length, 
     min: 0, 
     row: row, 
     _search: function (state) { 
      var minc = this._compare(this.table[this.min][this.column], state.row[this.column]); 
      var maxc = this._compare(this.table[this.max - 1][this.column], this.row[this.column]); 
      if (state.table[state.min][state.column] == state.table[state.max - 1][state.column]) { return; } 
      if (minc < 0) { state.max = state.min; return; } 
      if (maxc > 0) { state.min = state.max; return; } 
      if ((state.max - state.min) > 2) { 
       var mid = Math.ceil((state.min + state.max)/2); 
       var midc = state._compare(state.table[mid][state.column], state.row[state.column]); 
       if (midc < 0) { 
        state.max = mid; 
        state._search(state); 
        return; 
       } else if (midc > 0) { 
        state.min = mid; 
        state._search(state); 
        return; 
       } else { 
        for (var i = mid - 1; i >= state.min; i--) { if (state._compare(state.table[i][state.column], state.row[state.column]) != 0) { state.min = i + 1; break; } } 
        for (var i = mid + 1; i < state.max; i++) { if (state._compare(state.table[i][state.column], state.row[state.column]) != 0) { state.max = i; break; } } 
        return; 
       } 
      } else { 
       if (maxc < 0) { 
        if (minc > 0) { state.min = state.max - 1; state.max = state.max - 1; return; } 
        else { state.max = state.max - 1; return; } 
       } else if (minc > 0) { 
        state.min = state.max - 1; return; 
       } 
      } 
      return; 
     }, 
     table: table 
    }; 
    for (var i = 0; i < sort.length; i++) { 
     state.column = sort[i]; 
     state._search(state); 
     if (state.min >= state.max) { break; } 
    } 
    return ({ max: state.max, min: state.min }); 
} 

for (var i = 0; i < table.length; i++) { 
    document.write(table[i].i + '&nbsp;&nbsp;&nbsp;&nbsp;' + table[i].id+ '&nbsp;&nbsp;&nbsp;&nbsp;' + table[i].id2 + '&nbsp;&nbsp;&nbsp;&nbsp;' + table[i].id3 + '<BR />'); 
} 
var insertion = {i: 3, id: 0, id2: 1, id3: 1}; 
document.write(InsertionIndex(table, sort, insertion).min + '&nbsp;&nbsp;&nbsp;&nbsp;' + InsertionIndex(table, sort, insertion).max + '&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;2<BR />'); 
insertion = {i: 3, id: 1, id2: 1, id3: 1}; 
document.write(InsertionIndex(table, sort, insertion).min + '&nbsp;&nbsp;&nbsp;&nbsp;' + InsertionIndex(table, sort, insertion).max + '&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;3<BR />'); 
insertion = {i: 3, id: 2, id2: 1, id3: 1}; 
document.write(InsertionIndex(table, sort, insertion).min + '&nbsp;&nbsp;&nbsp;&nbsp;' + InsertionIndex(table, sort, insertion).max + '&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;9<BR />'); 
insertion = {i: 3, id: 3, id2: 1, id3: 1}; 
document.write(InsertionIndex(table, sort, insertion).min + '&nbsp;&nbsp;&nbsp;&nbsp;' + InsertionIndex(table, sort, insertion).max + '&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;10&nbsp;&nbsp;&nbsp;&nbsp;10<BR />');