Сортировка 2 или более массивных результатов?

Question

Мне нужно иметь возможность сортировать несколько промежуточных наборов результатов и вводить их в файл в отсортированном порядке. Сортировка основана на одном значении столбца / ключа. Каждая запись набора результатов будет списком значений (например, запись в таблице)

1. Промежуточные результирующие наборы получены путем запроса совершенно разных баз данных .
2. Промежуточные результирующие наборы уже отсортированы по некоторому ключу (или столбцу). Их необходимо объединить и снова отсортировать по одному и тому же ключу (или столбцу) перед записью в файл.
3. Поскольку эти наборы результатов могут быть массивными (порядка МБ), это невозможно сделать в памяти.

Мое решение в широком смысле:

Для использования хэша и файла произвольного доступа. Поскольку результирующие наборы уже отсортированы, при получении результирующих наборов я буду сохранять отсортированные значения столбцов в качестве ключей в хэш-карте. Значением в хеш-карте будет адрес в файле произвольного доступа, где каждая запись ассоциированное с этим столбцом значение будет сохранено .

Есть идеи?

Answer 1

иметь указатель на каждый набор, изначально указывающий на первую запись

Затем выберите следующий результат из набора, который предлагает самую низкую запись

Запишите эту запись в файл и увеличьте соответствующий указатель

У этого подхода в основном нет накладных расходов, а время равно O (n). (это Merge-Sort, кстати)

Редактировать

Чтобы уточнить: это слияние часть сортировки слиянием.

Answer 2

Если у вас есть 2 предварительно отсортированных набора результатов, вы должны иметь возможность выполнять их итерацию одновременно при записи выходного файла. Вам просто нужно сравнить текущую строку в каждом наборе: Простой пример (не готов для копирования и вставки!):

ResultSet a,b;
//fetch a and b
a.first();
b.first();
while (!a.isAfterLast() || !b.isAfterLast()) {
  Integer valueA = null;
  Integer valueB = null;

  if (a.isAfterLast()) {
    writeToFile(b);
    b.next();
  }
  else if (b.isAfterLast()) {
    writeToFile(a);
    a.next();
  } else {
    int valueA = a.getInt("SORT_PROPERTY");
    int valueB = b.getInt("SORT_PROPERTY");
    if (valueA < valueB) {
      writeToFile(a);
      a.next();
    } else {
      writeToFile(b);
      b.next();
    }
  }



}

Answer 3

Похоже, вы ищете реализацию алгоритма Balance Line .