MiddleCodeRareNot answered yet
Sort a huge byte file that does not fit in memory
A very large file holds elements of type byte (values 0..255) and does not fit in RAM. Write its sorted contents to another file.
Requirements:
- Do not load the whole file into memory.
- Exploit the fact that there are only 256 distinct byte values.
def sort_bytes(in_path, out_path):
# your code hereWrite the implementation.
Because the value range is bounded (256 byte values), use counting sort: stream the file in chunks, tally each byte's frequency in a 256-slot array, then write each value repeated by its count. This is O(n) time and O(1) extra memory (a fixed 256-entry table). The general unbounded case would need external merge sort: split into sorted runs on disk, then k-way merge them.
- ✗Trying to load the whole file into memory despite the size constraint
- ✗Missing that 256 bounded values enable O(n) counting sort
- ✗Assuming dict insertion order is the same as sorted-by-key order
- →Why does the bounded byte range turn this into an O(n) problem?
- →How would you sort the file if the values were unbounded 64-bit integers?
Contents
Task
Implement sort_bytes: write the sorted contents of a huge byte file to another file without loading it whole.
Solution
def sort_bytes(in_path, out_path, chunk=1 << 20):
counts = [0] * 256
with open(in_path, "rb") as f:
while True:
block = f.read(chunk)
if not block:
break
for b in block: # 0..255
counts[b] += 1
with open(out_path, "wb") as out:
for value, n in enumerate(counts):
if n:
out.write(bytes([value]) * n)Key points
- The range is bounded to 256 values → counting sort in O(n), O(1) memory.
- The file is read in chunks — only one block plus the 256-counter table is in RAM at once.
- Without a bounded range you would need external merge sort (runs + k-way merge).
Contents
