mergesort

README

mergesort

An on disk merge sort library written in go.

Provide methods to read records, write records, and compare records. This library will take a file of unsorted records, and give you a file of sorted records.

Documentation

See the full documentation

Build Status

Code Coverage

Documentation

Overview

Package mergesort is a library for performing an on-disk merge sort.

You provide a method to read, write, and compare records. The library will take a file containing unsorted records, and produce a file containing sorted records.

Index

• func MergeSort(unsortedFile, sortedFile *os.File, read ReadRecord, write WriteRecord, ...) error
• type CompareRecords
• type ReadRecord
• type WriteRecord

Functions

func MergeSort

func MergeSort(unsortedFile, sortedFile *os.File, read ReadRecord, write WriteRecord, compare CompareRecords, context interface{}, blockSize int) error

MergeSort takes records from the unsortedFile, sorts them, and produces a sortedFile containing the same records in sorted order. To do this, the call provides three methods ReadRecord, WriteRecord, and CompareRecords. You can optionally provide a context object, this object will be included in all calls to ReadRecord, WriteRecord, CompareRecords. The blockSize parameter will limit the total number of records that are sorted in memory at a single time.

NOTE: sortedFile is allowed to be the same as unsortedFile.

NOTE: Be sure to rewind unsortedFile first if just wrote it out. See https://github.com/mschoch/mergesort/issues/1

Types

type CompareRecords

type CompareRecords func(rec1, rec2 interface{}, context interface{}) int

CompareRecords is responsible for ordering records. Two records are provided, if rec1 is less than rec2, return -1. If rec1 is greater than rec2, return 1. If they are the same, return 0. The record objects could be anything produced by another ReadRecord call in the same MergeSort operation. The optional context object passed ot the original MergeSort operation is provided.

type ReadRecord

type ReadRecord func(file *os.File, context interface{}) (interface{}, error)

ReadRecord is responsible for reading a single record from the file. If an error occurs, return nil and the error. If the end of the file is reached, return io.EOF. The record object can be anything, but WriteRecord and CompareRecord calls in the same MergeSort operation must be able to work with it. The optional context object passed to the original MergeSort operation is provided.

type WriteRecord

type WriteRecord func(file *os.File, record interface{}, context interface{}) error

WriteRecord is responsible for writing a single record to the file. If an error occurs, return the error, otherwise nil. The record object could be anything produced by another ReadRecord call in the same MergeSort operation. The optional context object passed to the original MergeSort operation is provided.