Как сортировать быстрее при добавлении нескольких элементов в отсортированный список?

Question

У меня есть отсортированный список из ~ 10'000 элементов, в который я вставляю несколько элементов (1-10) за раз между появлением первого.Измерения показывают, что процедура сортировки занимает несколько миллисекунд (~ 5), предположительно потому, что lsort выполняет сортировку с нуля каждый раз.Теперь это занимает большую часть времени кадра, поэтому мне нужно что-то с этим сделать.

Есть ли хитрость для объединения большого отсортированного списка с небольшим отсортированным списком с повышенной эффективностью?

Код для объяснения контекста:

while {true} {
  set work [lindex $frontier 0]
  set frontier [lreplace $frontier 0 0]
  if {[done $work]} break;
  set more_work [do work]; # about 1-10 elements, distribution is generally hard to predict
  lappend frontier {*}$more_work
  set frontier [lsort $frontier]; # when frontier is 10'000 elements time to sort is ~5ms
}

Попытка приложить все усилия, чтобы реализовать процесс Tcl, выполняющий сортировку, подобную слиянию, опубликует результаты.: -)

Answer 1

Этот процесс сокращает время, прошедшее с ~ 5 мс до ~ 1,2 мс:

proc merge_insert {sorted1 sorted2} {
  set res {}
  set prevloc 0
  foreach insert $sorted2 {
    # find location of next element to insert
    set nextloc [lsearch -bisect -integer -index 1 $sorted1 [lindex $insert 1]]
    # append up to next loc
    lappend res {*}[lrange $sorted1 $prevloc $nextloc] $insert
    # put read location just beyond the inserted element
    set prevloc [+ 1 $nextloc]
  }
  # append whatever tail is left
  lappend res {*}[lrange $sorted1 $prevloc end]
  return $res
}

Атрибут, отсортированный по, является целым числом во втором элементе в каждом отсортированном элементе, следовательно, -integer index 1 и lindex $insert 1.