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

217

25 марта 2019, 04:50

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

Answer 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 - это сортировка подсчетом. Только вместо памяти используется диск.