利用归并排序算法对大文件进行排序

归并排序算法介绍，请参照Wikipeida

zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

基本思想：

大文件分割成行数相等的两个子文件，递归（归并排序）两个子文件，直到递归到分割成的子文件低于限制行数

低于限制行数的子文件直接排序

两个排序好的子文件归并到父文件

直到最后所有排序好的父文件归并到输入的大文件并返回

之前看了网上很多示例代码，写的很不简洁， 引入了过多的临时变量i, j, k等等， 导致程序基本没法看，

只好自己写了一个，没有很关心执行效率， 只求够用，以后有机会再优化一下吧。

Performance：

输入999999行

cost: 10140 MILLISECONDS

cost: 10 MICROSECONDS per line

JDK要求

Java 8

package com.java.sort.merge;

import com.google.common.base.Charsets;
import com.google.common.base.Stopwatch;
import com.google.common.base.Strings;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterators;
import com.google.common.collect.PeekingIterator;
import com.google.common.io.Files;
import org.apache.commons.io.FileUtils;
import org.apache.commons.io.IOUtils;
import org.apache.commons.io.LineIterator;
import org.apache.commons.io.filefilter.AndFileFilter;
import org.apache.commons.io.filefilter.PrefixFileFilter;
import org.apache.commons.io.filefilter.SuffixFileFilter;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import org.junit.AfterClass;
import org.junit.BeforeClass;
import org.junit.Test;

import java.io.File;
import java.io.FilenameFilter;
import java.io.IOException;
import java.io.Writer;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;


public class FileMergeSort {
    private static final Logger log = LogManager.getLogger();
    private static final long total = 999999L;
    private static final int limit = 9999;

    private static void cleanTempFiles() {
        FilenameFilter filter = new AndFileFilter(ImmutableList.of(new PrefixFileFilter("sort"), new SuffixFileFilter(".part")));
        ImmutableList.copyOf(FileUtils.getTempDirectory().listFiles(filter)).forEach(File::delete);
    }

    private static int lineNumber(File input) throws IOException {
        int count = 0;
        LineIterator iterator = FileUtils.lineIterator(input);
        while (iterator.hasNext()) {
            iterator.next();
            count++;
        }
        return count;
    }

    private static File split(File input, int from, int to) throws IOException {
        File part = File.createTempFile("sort", ".part");
        Long lineNumber = 0L;
        String line = null;
        List<String> lines = new ArrayList<>(to - from);
        LineIterator iterator = FileUtils.lineIterator(input);
        while (iterator.hasNext()) {
            if (lineNumber > to) break;
            line = iterator.next();
            if (lineNumber >= from && lineNumber <= to) {
                lines.add(line);
            }
            lineNumber++;
        }
        FileUtils.writeLines(part, lines);
        return part;
    }

    private static File merge(File source, File left, File right) throws IOException {
        PeekingIterator<String> leftLineIterator = Iterators.peekingIterator(FileUtils.lineIterator(left));
        PeekingIterator<String> rightLineIterator = Iterators.peekingIterator(FileUtils.lineIterator(right));
        String leftLine, rightLine;
        try (Writer writer = Files.newWriter(source, Charsets.UTF_8)) {
            writer.write("");
            while (leftLineIterator.hasNext() && rightLineIterator.hasNext()) {
                leftLine = leftLineIterator.peek();
                rightLine = rightLineIterator.peek();
                if (leftLine.compareTo(rightLine) < 0) {
                    writer.append(leftLine.concat(IOUtils.LINE_SEPARATOR));
                    leftLineIterator.next();
                } else {
                    writer.append(rightLine.concat(IOUtils.LINE_SEPARATOR));
                    rightLineIterator.next();
                }
            }
            while (leftLineIterator.hasNext()) {
                writer.append(leftLineIterator.next().concat(IOUtils.LINE_SEPARATOR));
            }
            while (rightLineIterator.hasNext()) {
                writer.append(rightLineIterator.next().concat(IOUtils.LINE_SEPARATOR));
            }
        }
        return source;
    }

    private static File directSort(File input) throws IOException {
        List<String> list = new ArrayList<>(limit);
        FileUtils.lineIterator(input).forEachRemaining(list::add);
        list.sort(String::compareTo);
        FileUtils.writeLines(input, list);
        return input;
    }

    public static File mergeSort(File input) throws IOException {
        int total = lineNumber(input);
        if (total <= limit) {
            return directSort(input);
        }
        int half = total / 2;
        File left = mergeSort(split(input, 0, half));
        File right = mergeSort(split(input, half + 1, total));
        return merge(input, left, right);
    }


    @BeforeClass
    public static void init() throws IOException {
        cleanTempFiles();
        int minLength = String.valueOf(total).length();
        try (Writer writer = Files.newWriter(new File("long.txt"), Charsets.UTF_8)) {
            writer.write("");
            for (long i = total; i > 0L; i--) {
                writer.append(Strings.padStart(String.valueOf(i), minLength, ‘0‘).concat(IOUtils.LINE_SEPARATOR));
            }
        }
    }

    @AfterClass
    public static void clean() {
        cleanTempFiles();
    }

    @Test
    public void testSort() throws IOException {
        Stopwatch watch = Stopwatch.createStarted();
        File sorted = mergeSort(new File("long.txt"));
        watch.stop();
        log.info(String.format("cost: %s MILLISECONDS", watch.elapsed(TimeUnit.MILLISECONDS)));
        log.info(String.format("cost: %s MICROSECONDS per line", watch.elapsed(TimeUnit.MICROSECONDS) / total));
    }

}

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.java.app</groupId>
    <artifactId>sample</artifactId>
    <version>1.0-SNAPSHOT</version>

    <dependencies>
        <dependency>
            <groupId>commons-io</groupId>
            <artifactId>commons-io</artifactId>
            <version>2.4</version>
        </dependency>       
        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>18.0</version>
        </dependency>        
        <dependency>
            <groupId>org.apache.logging.log4j</groupId>
            <artifactId>log4j-api</artifactId>
            <version>2.1</version>
        </dependency>
        <dependency>
            <groupId>org.apache.logging.log4j</groupId>
            <artifactId>log4j-core</artifactId>
            <version>2.1</version>
        </dependency>
        <dependency>
            <groupId>org.apache.logging.log4j</groupId>
            <artifactId>log4j-jcl</artifactId>
            <version>2.1</version>
        </dependency>
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.12</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
</project>

原文：http://ivarchen.iteye.com/blog/2179500