External sorting is usually used when you need to sort files that are too large to fit into memory.
The trick is to break the larger input file into k sorted smaller chunks and then merge the chunks into a larger sorted file. For the merge use a min heap. k will depend on your memory threshold.
Read a certain number of records (depending on your memory threshold) from each chunk and put it in a queue per chunk.
Pop the leftmost item (This will be the smallest item as the items in the queue will be sorted) from each queue and push it to the heap
Pop the min item from the heap. Note what queue it came from
Replenish the queue with the next item from it's corresponding chunk that is not in the queue
Pop the left most item from the queue and push it to the heap
Write the min item to the output file
Continue the above 4 steps till the heap is empty
Sample python code (Does not merge in place)
import os
import heapq
import itertools
import linecache
from collections import deque
import sys
def external_sort(input_directory, input_file_name, output_file_name):
with open(os.path.expanduser(input_directory + '/' + output_file_name), 'w+') as f:
heap = []
pages = {}
next_line_numbers = {}
has_more_items = {}
chunk_file_paths, max_chunk_size = create_sorted_chunks(input_directory, input_file_name)
max_page_size = max_chunk_size // 10
for chunk_file_path in chunk_file_paths:
pages[chunk_file_path] = populate_page(chunk_file_path, max_page_size)
next_line_numbers[chunk_file_path] = len(pages[chunk_file_path])
has_more_items[chunk_file_path] = True
for chunk_file_path in chunk_file_paths:
heapq.heappush(heap, pages[chunk_file_path].popleft())
while heap:
item, chunk_file_path = heapq.heappop(heap)
f.write(str(item)+'\n')
if has_more_items[chunk_file_path]:
has_more_items[chunk_file_path] = append_next(pages, chunk_file_path, next_line_numbers[chunk_file_path])
next_line_numbers[chunk_file_path] += 1
if pages[chunk_file_path]:
heapq.heappush(heap, pages[chunk_file_path].popleft())
for chunk_file_path in chunk_file_paths:
os.remove(chunk_file_path)
def populate_page(chunk_file_path, max_page_size):
chunk = deque()
with open(chunk_file_path, 'r') as f:
for line in itertools.islice(f, 0, max_page_size):
chunk.append((int(line), chunk_file_path))
return chunk
def append_next(chunks, chunk_file_path, line_number):
chunk = chunks[chunk_file_path]
item = linecache.getline(chunk_file_path, line_number)
if item and len(item) > 0:
chunk.append((int(item), chunk_file_path))
has_more = True
else:
has_more = False
return has_more
def create_sorted_chunks(input_file_directory, input_file_name):
input_file_path = os.path.expanduser(input_file_directory + '/' + input_file_name)
suffix = 1
begin, end, tot = 0, 0, 0
chunk_file_paths = []
with open(input_file_path, 'r') as f:
for line in f.readlines():
tot += 1
end = tot//10
while suffix <= 10:
buffer = []
chunk_file_name = 'temp' + str(suffix) + '.txt'
chunk_file_path = os.path.expanduser(input_file_directory + '/' + chunk_file_name)
if not os.path.isfile(chunk_file_path):
with open(os.path.expanduser(input_file_path), 'r') as f:
for line in itertools.islice(f, begin, end):
buffer.append(int(line))
create_chunk(chunk_file_path, buffer)
suffix += 1
begin = end
end += tot//10
chunk_file_paths.append(chunk_file_path)
return chunk_file_paths, tot//10
def create_chunk(chunk_file_path, buffer):
buffer.sort()
with open(chunk_file_path, 'w+') as f:
for i in buffer:
f.write(str(i) + '\n')
if __name__ == '__main__':
external_sort(sys.argv[1], sys.argv[2], sys.argv[3])