Member Avatar for Diamonddrake

I have hit a slump, my line sorting text program runs out of memory when sorting large files, the answer is using an external merge sort. basically it breaks the file into chunks, sorts them, then loads chunks of the chunks, and sorts them, then some how comes up with a fully sorted file.

I have searched the internet, with multiple search engines, for hours the past couple of days. I can't seem to find any help what so ever on this topic, I have found facts that it exists, its purpose reiterated hundreds of times, but no information on how to do it, not even a link to a book I could buy.

Im not a student trying to cheat, or a developer trying to make millions on a program. I write freeware apps, and this one is being created out of necessity, for myself and some of the company I keep.

Please Help!!!

  • 3 Contributors
  • 5 Replies
  • 277 Views
  • 2 Years Discussion Span
  • Latest Post Latest Post by stefansavev

Dani AI

Generated

correctly identified external merge sort as the solution. The practical outline below fills the implementation gap left in the thread (thanks to for offer to inspect code and to for pointing to an implementation). The approach is split into two phases: produce sorted runs that fit memory, then perform a k‑way merge of those runs.

Phase 1 — produce runs: read the CSV in memory-sized chunks, sort each chunk with Python’s list.sort(key=...), and write each sorted chunk to a temporary file (use tempfile.NamedTemporaryFile(delete=False) and csv.writer). Chunk sizing is critical: pick a line count or byte budget that keeps Python memory usage below the available RAM (measure with small tests and leave headroom for interpreter overhead).

import csv, tempfile

def make_runs(in_path, chunk_lines, key_func):
    runs = []
    with open(in_path, newline='') as inf:
        reader = csv.reader(inf)
        chunk = []
        for row in reader:
            chunk.append(row)
            if len(chunk) >= chunk_lines:
                chunk.sort(key=key_func)
                tf = tempfile.NamedTemporaryFile(delete=False, mode='w', newline='')
                csv.writer(tf).writerows(chunk)
                tf.close()
                runs.append(tf.name)
                chunk = []
        if chunk:
            chunk.sort(key=key_func)
            tf = tempfile.NamedTemporaryFile(delete=False, mode='w', newline='')
            csv.writer(tf).writerows(chunk)
            tf.close()
            runs.append(tf.name)
    return runs

Phase 2 — merge runs: perform a memory-efficient k‑way merge using heapq.merge or a small heap. Decorate rows with (key, run_index, row) so comparisons never fall back to comparing full rows (avoids type/format issues). Stream merged rows straight to an output CSV — no full-file buffering.

import heapq, csv

def merge_runs(run_paths, out_path, key_func):
    files = [open(p, newline='') for p in run_paths]
    readers = [csv.reader(f) for f in files]
    def decorate(r, i):
        for row in r:
            yield (key_func(row), i, row)
    merged = heapq.merge(*[decorate(r, i) for i, r in enumerate(readers)])
    with open(out_path, 'w', newline='') as outf:
        w = csv.writer(outf)
        for _k, _i, row in merged:
            w.writerow(row)
    for f in files:
        f.close()

Notes and cautions: CSVs with embedded newlines require newline='' and proper dialect handling. OS file‑descriptor limits may force multi‑pass merging (merge N runs into one, repeat). Convert sort keys to consistent types (ints, datetimes) before sorting. Delete temp files after successful merge. Test on synthetic data first to tune chunk size and IO buffers.

Recommended Answers

All 5 Replies

Member Avatar for LizR

Is the data you're sorting confidential in anyway? eg, if I asked you to PM me a link to a copy of your source and the data thats failing.. would you be prepared to place it somewhere I could get at it, so I could take a look?

Member Avatar for Diamonddrake

the data I am using is a data file from a fiend of mines employer, it was the only suitable file for testing, and I am afraid it is confidential. but its just a large csv file. the code for the sorting method I posted here. all i can tell is that i need to use external sorting to handle large files. but i can't see to find any information on how to implement it.

Member Avatar for LizR

OK, but I was more after the entire code, so I could recreate the issue.. A segment is not sufficient to do that.

If you could post a link to the code and how to create a similar but fake csv file (eg how many fields, how many lines, data types if necessary to make the sort work) I can take a look

Member Avatar for Diamonddrake

pm me your email addy and I will send it to you as an attachment.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.