Сортировка и слияние данных из разных файлов в один

Для ускорения поможет буфер чтения. Просто читаем несколько чисел и их заносим в двумерный массив. А алгоритм слияния стандартный :

• Находим минимальное число из первых, что хранятся в буфере
• Вычёркиваем этот один элемент из буфера

Вот как реализовал буфера :

// несколько чисел на каждый файл
int64_t bufer [ filesN ] [ bufsize ] ;

// индекс первого числа
int buferindex [ filesN ] ;

// количество чисел заполнено
int bufersize [ filesN ] ;

// флаг конец файла достигнут
bool fileseof [ filesN ] ;

Функции в реализации :

читаю первое число, что находится в буфере i-го файла и записываю в указанное место памяти, возвращаю true или false

bool  buffirst ( int  , int64_t *  ) ;

удаляю первый элемент из буфера i-го файла

void  popfirst ( int ) ;

нахожу минимальное число из доступных первых, записываю результат в место памяти, удаляю этот элемент из буфера, возвращаю true или возвращаю false

bool  findmin ( int64_t * ) ;

в главной функции просто нахожу минимальное число с помощью findmin , и записываю в файл

Тестировал в Си и плюсах такой код :

// gcc -std=c11 -Os main.c -o main
// g++ -x c++ -std=c++11 -Os main.c -o mainpp
# include <errno.h>
# include <string.h>
# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>
# include <stdint.h>
char const * files [ ] = { "test1.txt" , "test2.txt" , "test3.txt" ,
  "test4.txt" , "test5.txt" , "test6.txt" } ;
char  const fileo [ ] = "test.txt" ;
enum { filesN = sizeof ( files ) / sizeof ( files [ 0 ] ) } ;
FILE * fa [ filesN ] ;
FILE * fo ;
enum { bufsize = 12 } ;
int64_t bufer [ filesN ] [ bufsize ] ;
int buferindex [ filesN ] ;
int bufersize [ filesN ] ;
bool fileseof [ filesN ] ;

// читаю первое число, что находится в
// буфере [filei] файла и записываю в * xp , возвращаю true
// или возвращаю false
bool  buffirst ( int const filei , int64_t * const xp ) {
  int const ind = buferindex [ filei ] ;
  if ( ind < bufersize [ filei ] ) {
    * xp = bufer [ filei ] [ ind ] ;
    return  true ;
  }
  if ( fileseof [ filei ] )
    return false ;
  bufersize [ filei ] = 0 ;
  { int i = 0 ;
    do {
      if ( fscanf ( fa [ filei ] , "%ld" ,
        & ( bufer [ filei ] [ i ] ) ) != 1 ) {
        fileseof [ filei ] = true ;
        break ;
      } // if scanf
      ++ ( bufersize [ filei ] ) ;
      ++ i ;
    } while ( i < bufsize ) ;
  } // i
  if ( bufersize [ filei ] == 0 ) 
    return false ;
  * xp = bufer [ filei ] [ 0 ] ;
  buferindex [ filei ] = 0 ;
  return  true ;
}

// удаляю первый элемент из буфера [ bestfile ] файла
static inline void  popfirst ( int const bestfile ) {
  ++ ( buferindex [ bestfile ] ) ;
}

// нахожу минимальное число из доступных первых,
// записываю результат в место памяти,
// удаляю этот элемент из буфера, возвращаю true
// или возвращаю false
bool  findmin ( int64_t * const xp ) {
  int64_t min ; 
  int bestfile ;
  bool found = false ;
  for ( int i = 0 ; i < filesN ; ++ i ) {
    int64_t x ;
    if ( buffirst ( i , & x ) ) {
      if ( found ) {
        if ( x < min ) {
          min = x ; 
          bestfile = i ;
        }
      }
      else {
        min = x ;
        bestfile = i ;
        found = true ;
      }
    } // if buffirst
  } // for i
  if ( found ) {
    * xp = min ;
    popfirst ( bestfile ) ;
  }
  return  found ;
}

// нахожу минимальное число с помощью findmin , и записываю в файл
int main ( ) {  
  for ( int i = 0 ; i < filesN ; ++ i ) {
    fa [ i ] = fopen ( files [ i ] , "r" ) ;
    if ( fa [ i ] == NULL ) {
      fprintf(stderr,"fopen ( `%s` ) : %s\n",files [ i ],strerror(errno));
      exit ( 1 ) ;
    }
  } // for i
  fo = fopen ( fileo , "w" ) ;
  if ( fo == NULL ) {
      fprintf(stderr,"fopen ( `%s` ) : %s\n",fileo,strerror(errno));
      exit ( 1 ) ;
    }
  do {
    int64_t x ;
    if ( findmin ( & x ) ) {
      if ( fprintf ( fo , "%ld " , x ) < 0 ) {
        fputs("fprintf ( fo , \"%ld \" , x )\n",stderr);
        exit ( 1 ) ;
      }
    }
    else
      break ;
  } while ( true ) ;
  if ( fclose ( fo ) ) {
    fprintf(stderr,"fclose ( `%s` ) : %s\n",fileo,strerror(errno));
    exit ( 1 ) ;
  }
  for ( int i = 0 ; i < filesN ; ++ i ) {
    if ( fclose  ( fa  [ i ] ) ) {
      fprintf(stderr,"fclose ( `%s` ) : %s\n",files [ i ],strerror(errno));
      exit ( 1 ) ;
    }
  } // for i
}

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

Примечания:

• идея алгоритма родилась из того что командой cat в linux и type в windows можно объединить файлы превышающие объем оперативки (я проверял на linux)
• для демонстрации вместо файлов я использую массивы таким образом алгоритм легко протестировать даже в браузере
• алгоритм гарантирует что левый(первый) файл не содержит числа превышающего любое из чисел в правом(следующем) файле
• минусом алгоритма является то что он не гарантирует размещение в памяти отдельного файла (но частично это настраивается, хотя решение не полное если файл с одинаковыми числами не влезет в память)

Основной алгоритм:

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

Пример вывода:

Отсортированные файлы:
[ 31, 42, 94, 99, 106 ] [ 6, 109, 133, 135, 141 ] [ 6, 50, 57, 118, 126 ]
{ min: 6, max: 141, maxSizeFile: 17 }
Проверка превышения размера файла: Все хорошо
Проверка сортировки: Все хорошо
[ 6, 6, 31, 42, 50, 57, 94, 99, 106, 109, 118, 126, 133, 135, 141 ]
Запуск теста на 10000 итераций
{ errors: { testOversize: 1, testEqual: 0 }}

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

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

function test(log = console.log){
  let errors = {
    testOversize : 0,
    testEqual: 0
  }
  // массивы как файлы
  // генерируем для примера
  const a = Array.from(Array(5)).map(e => Math.floor(Math.random() * 150)) 
  const b = Array.from(Array(5)).map(e => Math.floor(Math.random() * 150)) 
  const c = Array.from(Array(5)).map(e => Math.floor(Math.random() * 150)) 

  // сколько файлов создать,
  // лучше больше чем есть так как числа могут совпадать
  // а это значит что один файл может стать больше чем положено
  const COUNT_FILES = 100 
  // вместимость в процентах на один файл
  const FIT_FILE = (100 / COUNT_FILES) 

  // функция сортировки чисел
  const numSort = (a, b)  => { if (a === b) return 0; return Math.sign(a - b)}

  ///////////////////////////////////////////////////////////////////////
  // 1)  отсортировать файлы по отдельнсоти
  const a1 = a.sort(numSort)
  const b1 = b.sort(numSort)
  const c1 = c.sort(numSort)

  log('Отсортированные файлы:\n', a1, b1, c1)

  ///////////////////////////////////////////////////////////////////////
  // 2) найти минимум, максимум чисел
  // и максимальный размер одного файла (для теста алгоритма)
  let max = -Infinity // начинаем с наименьшего
  let min = Infinity  // начинаем с наибольшего
  let maxSizeFile = 0 // начинаем с 0

  for (arr  of [a1, b1, c1]){
    if (min > arr[0]) min = arr[0]
    if (max < arr[arr.length -1]) max = arr[arr.length -1]  
    sizeFile = arr.join(' ').length // получаем размер файла в байтах (для теста)
    if (maxSizeFile < sizeFile) maxSizeFile = sizeFile 
  }

  log({min, max, maxSizeFile})

  ///////////////////////////////////////////////////////////////////////
  // 3) раскидать данные в новые файлы

  files = {} // массивы как файлы в объекте (только для демонстрации)
  // cоздаем нужное количество массивов (файлов)
  for (let n = 0; n < COUNT_FILES; n++){
    // например files['file0'] = []  file0 инициализируем пустым массивом
    files[`file${n}`] = []  
  }

  // имена файлов, 
  // порядок важен в первый файл меньшие числа
  // в последний большие 
  filesKey = Object.keys(files) 

  for (arr  of [a1, b1, c1]){
    for (n of arr){
      k = ((n - min) * 100) / (max - min) // нахождение позиции
      f = Math.floor(k / (FIT_FILE + 1)) // индекс файла для числа
      files[filesKey[f]].push(n)  // записть в файл по имени (индексу)
    }
  }

  ///////////////////////////////////////////////////////////////////////
  // 4) после заполнения файлов сортируем каждый из них
  for (fileKey of Object.keys(files)){
    files[fileKey].sort(numSort)
  }

  // содержимое файлов
  // log(JSON.stringify(files))

  // объединение файлов
  // можно выполнить консольной коммандой перенаправления
  // (ее можно вызвать из C++ кода)
  // cat file1 file2 > newfile - для linux
  // type file1 file2 > newfile - для windows
  result = Object.values(files).reduce((acc,  e) => [...acc, ...e], [])

  // 5) на данном этапе все выполнено, осталось сделать проверки
  sizes = Object.values(files).map(e => e.join(' ').length)

  const testOversize = sizes.some(e => e > maxSizeFile)
  if (testOversize) errors.testOversize = 1 
  log(testOversize
      ? 'Проверка превышения размера файла: Размер превышен' + sizes.some(e => e > maxSizeFile)
      : 'Проверка превышения размера файла: Все хорошо')

  testEqual = result.join(' ') === [...a, ...b, ...c].sort(numSort).join(' ')
  if (!testEqual) errors.testEqual = 1 
  log(testEqual
      ? 'Проверка сортировки: Все хорошо' 
      : 'Проверка сортировки: Ошибка')

  //выводим результирующий массив (файл)
  log(result)
  return errors
}

test()

const nope = () => {}

const iter = 10000
console.log(`Запуск теста на ${iter} итераций`)
let errors = {
  testOversize : 0,
  testEqual: 0
}
for(let i=0; i < iter; i++) {
  const {testEqual, testOversize} = test(nope)  
  errors.testEqual += testEqual
  errors.testOversize += testOversize
}
console.log({errors})