Java External Sort Implementation
Budget: $30 – $250 USD
I need an experienced Java developer to implement an external sorting system for binary data files. The program must sort large datasets that cannot fit into memory, using replacement selection (for run generation) and multi-way merge (for the final sorted output). This is a performance-critical project that requires careful handling of binary I/O, buffer management, and algorithmic correctness.
- Data Format
The input file consists of binary records:
* Block size: 8,192 bytes
* Record size: 16 bytes
* First 8 bytes: long (record ID)
* Second 8 bytes: double (record key – sorting field)
* Each block: 512 records
* File contains at least 8 blocks
- Required Algorithm
The solution must implement:
---
1. Replacement Selection (Run Building)
- Use 8 blocks of memory as the working heap.
- Use 1 input buffer block and 1 output buffer block.
- Read first 8 blocks into memory.
- Generate the longest possible runs, writing them to a temporary run file.
- Output is buffered: write to disk only when the 8,192-byte buffer is full.
- Each new run should start at the beginning of a block in the run file.
2. Multi-Way Merge (Run Merging)
- Merge all generated runs into the final sorted file.
- Use the same 8-block memory area to store run fragments during merges.
- Use:
* 1 block per run being merged
* 1 block output buffer
- Perform as many merge passes as required depending on number of runs.
* Must use random-access I/O (seek()) for reading the run file.
* Output is sequential.
- Technical Requirements
* Must be implemented in Java.
* Must use ByteBuffer for serialization/deserialization.
Javadocs: (https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/nio/ByteBuffer.html)
* The program is invoked as:
```
java Externalsort <filename>
```
* The program modifies the input file (sorting in-place).
* Provide well-structured, commented, production-quality code.
---
- Output Requirements
After sorting:
Print to standard output:
* The first record of every 8,192-byte block in the final sorted file.
* Print 5 records per line.
* Each record must include key value + id value, separated by whitespace.
* Formatting must match exactly (sample output will be provided).
- Deliverables
* Externalsort.java (program with `main()`).
* All supporting classes.
* Clean, readable, commented source code.
* Instructions to compile and run.
* Brief document explaining:
* Run generation logic
* Merge strategy
* Memory/block handling
- Ideal Freelancer
* Strong Java experience
* Familiarity with external sorting algorithms
* Comfortable with binary I/O, ByteBuffer, and random-access files
* Understanding of heaps, run generation, and k-way merges
- Data Format
The input file consists of binary records:
* Block size: 8,192 bytes
* Record size: 16 bytes
* First 8 bytes: long (record ID)
* Second 8 bytes: double (record key – sorting field)
* Each block: 512 records
* File contains at least 8 blocks
- Required Algorithm
The solution must implement:
---
1. Replacement Selection (Run Building)
- Use 8 blocks of memory as the working heap.
- Use 1 input buffer block and 1 output buffer block.
- Read first 8 blocks into memory.
- Generate the longest possible runs, writing them to a temporary run file.
- Output is buffered: write to disk only when the 8,192-byte buffer is full.
- Each new run should start at the beginning of a block in the run file.
2. Multi-Way Merge (Run Merging)
- Merge all generated runs into the final sorted file.
- Use the same 8-block memory area to store run fragments during merges.
- Use:
* 1 block per run being merged
* 1 block output buffer
- Perform as many merge passes as required depending on number of runs.
* Must use random-access I/O (seek()) for reading the run file.
* Output is sequential.
- Technical Requirements
* Must be implemented in Java.
* Must use ByteBuffer for serialization/deserialization.
Javadocs: (https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/nio/ByteBuffer.html)
* The program is invoked as:
```
java Externalsort <filename>
```
* The program modifies the input file (sorting in-place).
* Provide well-structured, commented, production-quality code.
---
- Output Requirements
After sorting:
Print to standard output:
* The first record of every 8,192-byte block in the final sorted file.
* Print 5 records per line.
* Each record must include key value + id value, separated by whitespace.
* Formatting must match exactly (sample output will be provided).
- Deliverables
* Externalsort.java (program with `main()`).
* All supporting classes.
* Clean, readable, commented source code.
* Instructions to compile and run.
* Brief document explaining:
* Run generation logic
* Merge strategy
* Memory/block handling
- Ideal Freelancer
* Strong Java experience
* Familiarity with external sorting algorithms
* Comfortable with binary I/O, ByteBuffer, and random-access files
* Understanding of heaps, run generation, and k-way merges