Skip to content

And390/external_sort

Folders and files

NameName
Last commit message
Last commit date

Latest commit

Sep 30, 2018
59df5d2 · Sep 30, 2018

History

6 Commits
Apr 3, 2016
Sep 29, 2015
Sep 5, 2015
Sep 29, 2015
Sep 29, 2015
Sep 30, 2018

Repository files navigation

External sort example

This code implements the external merge sort algorithm. It uses fixed-size memory buffer and disk space (one or two files) to sort arbitrary input data. Interface:

void sort(char* filename, char* temp_filename, size_t buff_size,
          f_produce produce, f_get_size get_size, f_compare compare, void* context);
typedef void* (*f_produce) (void* data, size_t capacity, void* context);
typedef size_t (*f_get_size) (void* data, size_t capacity, void* context);
typedef bool (*f_compare) (void* p1, void* p2);

The main function sort does all the work. You need to provide data items using produce function. Items can be of different sizes, so you must pass get_size function because the size of the items is not stored. At the first step sort accumulates data parts of buffer size from produce, sorts each part and writes it to disk. If there were more than one part, then at the second step it reads the previous file and merges all parts into the result file.

This example uses Single Compilation Unit principle. To build it you only need to specify one file only once (include and use src/extsort.cpp or compile test/test.cpp).

See test/test.cpp for example and more detailed comments in src/extsort.cpp.

About

External merge sort algorithm implementation example

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published