Алгоритм сортировки большого файла с со сложностью приближенной к O(2n)

#java #алгоритм #многопоточность #сортировка

Есть файл размером 1Гб который содержит FLOAT в бинарном виде, т.е. 4 байта на 1
значение. Как реализовать сортировку такого файла с применением многопоточности и с
ограничением RAM 128mb и чтобы сложность алгоритма сортировки была приближена к O(2n)?
    

Ответы

Ответ 1

Псевдокод

valueBytes = Float.bytes
input = new File(name = 'input')
counterBytes = minBytesToFit(ceil(input.size/valueBytes))

temp = CreateFile(name = 'temp', size = maxNumberFor(bytes = valueBytes)*counterBytes
+ counterBytes, fill = 0)
output = CreateFile(name = 'output', size = input.size)

for(i=0; input.size/valueBytes; i++){
    current=input.readNumber(offset = i*valueBytes, count = valueBytes)
    currentTemp = temp.readNumber(offset = current, count = counterBytes)
    currentTemp++
    temp.writeNumber(offset = current, count = counterBytes, value = currentTemp)
}

for(i=0; temp.size/counterBytes; i++){
    current = temp.readNumber(offset = i*counterBytes, count = counterBytes)
    out.append(value = i, count = current, blockSize = valueBytes)
}


PS Как заметил @MBo - это сортировка подсчетом. Только вместо памяти используется диск.