This package is written to sort a lot of data, which can not be done in memory.

Install

npm install big-data-sort

Usage

Give an input file which contains elements separated by specific separator, the function write sorted elements to output file with the same separator.

const sort = require('big-data-sort')

// return Promise
sort({
  input: '/path/to/input/file',
  output: '/path/to/output/file',
  sep: '\n',
  compare: (a, b) => Number(a) - Number(b)
})

Algorithm

/* origin file */
4 3 5 2 1 7 6 9 0

/* step1: mark file as blocks */
4 3 5 | 2 1 7 | 6 9 0

/* step2: sort every block & write to new file */
3 4 5 | 1 2 7 | 0 6 9

/* step3: read one number from each block to make up a heap */
    0
  /   \
 1     3

/* step4: pick the top element & write to result file. */
0

/**
 * step5: read a new number from the block in which the top element is.
 * if the block is used up, move the last element to heap top. 
 */
    6
  /   \
 1     3

/* step6: adjust the heap */
    1
  /   \
 6     3

/* loop step4, step5, step6 until all blocks are used up. */
0 1 2 3 4 5 6 7 9

Test

clone this repo & run npm install, npm run build, npm test