Skip to content

Instantly share code, notes, and snippets.

@nandakoryaaa
Last active February 16, 2023 22:02
Show Gist options
  • Save nandakoryaaa/c17a3f9b49a515d9ce3f43458beb2221 to your computer and use it in GitHub Desktop.
Save nandakoryaaa/c17a3f9b49a515d9ce3f43458beb2221 to your computer and use it in GitHub Desktop.
Merge sort implementing true external sequential file/stream emulation
def read_chunk(dst, src, chunk_size, pos, len_src):
while chunk_size > 0 and pos < len_src:
dst.append(src[pos])
pos += 1
chunk_size -= 1
return pos
def get_bingo_size(pos, chunk_size, len_src):
if pos + chunk_size > len_src:
return len_src - pos
return chunk_size
input = (9,0,7,8,3,11,1,5,0,5,10)
len_input = len(input)
chunk_size = 1
va = None
vb = None
while chunk_size < len_input:
a = []
b = []
pos = 0
while pos < len_input:
pos = read_chunk(a, input, chunk_size, pos, len_input)
pos = read_chunk(b, input, chunk_size, pos, len_input)
pos_a = 0
pos_b = 0
len_a = len(a)
len_b = len(b)
input = []
while True:
bingo_a = get_bingo_size(pos_a, chunk_size, len_a)
bingo_b = get_bingo_size(pos_b, chunk_size, len_b)
if bingo_a + bingo_b == 0:
break
read_a = bingo_a > 0
read_b = bingo_b > 0
write_a = False
write_b = False
while True:
if read_a:
va = a[pos_a]
pos_a += 1
write_a = True
if read_b:
vb = b[pos_b]
pos_b += 1
write_b = True
if write_a and write_b:
if va < vb:
read_b = write_b
write_b = False
else:
read_a = write_a
write_a = False
if write_a:
input.append(va)
write_a = False
bingo_a -= 1
read_a = bingo_a > 0
write_b = read_b
read_b = False
elif write_b:
input.append(vb)
write_b = False
bingo_b -= 1
read_b = bingo_b > 0
write_a = read_a
read_a = False
else:
break
chunk_size *= 2
print(input)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment