Линии Mergesort из файла .txt

Question

У меня есть файл с несколькими отсортированными строками. Теперь я хочу отсортировать все эти строки в одной объединенной строке в новом файле. Без загрузки всех номеров сразу.

Это часть моего файла:

12,86,280,304,350,359,371,391,405,548, 
 
255,264,325,346,435,466,483, 
 
39,114,214,298,317,377,428,438,575, 
 
35,165,183,281,336,367,386,418,438,593, 
 
44,77,97,117,122,156,251,415,533, 
 
109,155,163,172,212,226,340,358,452,577,592, 
 
33,74,91,204,256,307,357,388,534,552,554,570, 
 
50,99,246,309,345,358,395,405,419,425,566,

Теперь я хочу, чтобы объединить рода тех, так я сначала нужно знать, сколько строк в файле есть. Затем мне нужно получить все первые элементы и сравнить их. Самый низкий я пишу в новый файл. Затем я должен получить второй номер из строки, которую я только что написал. И сравните их с первыми номерами других строк. Как мне это сделать. Я написал для ArrayLists слиянием:

 //as long as there is unsorted data 
 
     while (listOfOutputs.size() > 0) { 
 
      //Set the lowest undefined 
 
      List<Integer> lowest = null; 
 
      for (List<Integer> list : listOfOutputs) { 
 
       //if the lowest is undefined, I'm the lowest 
 
       if (lowest == null) { 
 
        lowest = list; 
 
        //Else am I lower then the lowest? Then I'm the lowest 
 
       } else if (list.get(0) < lowest.get(0)) { 
 
        lowest = list; 
 
       } 
 
      } 
 

 
      //Finally the lowest is added to the sorted list and removed to from his own list. 
 
      assert lowest != null; 
 
      sortedList.add(lowest.remove(0)); 
 

 
      //Is the size of the list which contained to lowest now 0, remove him from the listOfOutputs 
 
      if (lowest.size() == 0) listOfOutputs.remove(lowest); 
 
     }

Но я не знаю, как переписать это в тот, который сортирует мой файл. Как это сделать, не загружая их в списки.

Sven

Answer 1

Вы можете использовать простой 2 способ слияния объединить 2 линии в то время, в одной линии, повторяя процесс, пока один отсортированный линия производится.

или

Предполагая, что к этому число строк, вы можете реализовать к пути слияния, вероятно, использует кучу для оптимизации поиска, какая линия имеет наималейший первый элемент. Каждый кучный элемент содержит ссылку на строку и эквивалент индекса (или указателя) на текущий элемент для этой строки. Куча упорядочивается текущими элементами каждой строки, так что голова кучи ссылается на линию с текущим наименьшим элементом. Куча инициализируется первыми элементами всех k строк.

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

Когда конец линии достигнут, слияние сводится к слиянию k-1, в конечном итоге заканчивается только одной строкой, которая копируется на объединенный вывод.