Various Java methods to create one sorted list from two sorted lists

TestSortedListStreams.java

package testsortedliststreams;

import java.util.*;
import java.util.stream.*;

/*
Sample output on late-2013 MacBook Pro:

Starting Naive List Sort, via Collections
Total number of sorted values: 40000000
Total execution time: 2514
Starting Naive List Sort, via Streams
Total number of sorted values: 40000000
Total execution time: 2286
Starting Naive List Sort, via Streams without conversion
Total number of sorted values: 40000000
Total execution time: 1965
Starting Sorted List Sort
Total number of sorted values: 40000000
Total execution time: 1752
*/

public class TestSortedListStreams {

    public static void main(String[] args) throws Exception {
        // Create two sorted lists
        List<Double> random1 = Collections.unmodifiableList(Stream.generate(Math::random).limit(20000000)
                .sorted().collect(Collectors.toList()));
        List<Double> random2 = Collections.unmodifiableList(Stream.generate(Math::random).limit(20000000)
                .sorted().collect(Collectors.toList()));

        rest();
        naiveListSort(random1, random2);
        rest();
        sortStreams(random1, random2);
        rest();
        sortStreamsNoConvert(random1, random2);
        rest();
        fasterListSort(random1, random2);
    }

    private static void naiveListSort(List<Double> first, List<Double> second) {
        System.out.println("Starting Naive List Sort, via Collections");
        long starttime = System.currentTimeMillis();

        List<Double> combinedList = new ArrayList(first.size() + second.size());
        combinedList.addAll(first);
        combinedList.addAll(second);
        Collections.sort(combinedList);

        System.out.println("Total number of sorted values: " + combinedList.size());
        System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime));
        // uncomment to print
        //combinedList.stream().forEach(System.out::println);
    }
    
    private static void sortStreams(List<Double> first, List<Double> second) {
        System.out.println("Starting Naive List Sort, via Streams");

        long starttime = System.currentTimeMillis();
        
        Stream<Double> random1 = first.stream();
        Stream<Double> random2 = second.stream();
        Stream<Double> combined = Stream.concat(random1, random2).sorted();
        List<Double> combinedList = combined.collect(Collectors.toList());

        System.out.println("Total number of sorted values: " + combinedList.size());
        System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime));
        // uncomment to print
        //combinedList.stream().forEach(System.out::println);
    }

    private static void sortStreamsNoConvert(List<Double> first, List<Double> second) {
        System.out.println("Starting Naive List Sort, via Streams without conversion");

        long starttime = System.currentTimeMillis();
        
        Stream<Double> random1 = first.stream();
        Stream<Double> random2 = second.stream();
        Stream<Double> combined = Stream.concat(random1, random2).sorted();

        System.out.println("Total number of sorted values: " + combined.count());
        System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime));
        // uncomment to print
        //Stream.concat(first.stream(),second.stream()).sorted().forEach(System.out::println);
    }
    
    // take advantage of the fact that both lists are sorted
    private static void fasterListSort(List<Double> first, List<Double> second) {
        System.out.println("Starting Sorted List Sort");
        long starttime = System.currentTimeMillis();
        
        List<Double> combinedList = new ArrayList(first.size() + second.size());
        
        int i = 0; // first index
        int j = 0; // second index
        int firstsize = first.size();
        int secondsize = second.size();
        while (i < firstsize) {
            while (first.get(i) >= second.get(j)) {
                combinedList.add(second.get(j++));
                if (j >= secondsize) {
                    break;
                }
            }
            combinedList.add(first.get(i));
            if (j >= second.size()) {
                break;
            }
            i++;
        }
        if (j < second.size()) {  // add remaining
            combinedList.addAll(second.subList(j, secondsize));
        } else if (i < first.size()) {
            combinedList.addAll(first.subList(i+1, firstsize));
        }
        System.out.println("Total number of sorted values: " + combinedList.size());
        System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime));
        // uncomment to print
        //combinedList.stream().forEach(System.out::println);
    }
    
    private static void rest() throws Exception {
        System.gc();
        Thread.sleep(5000);
    }
}

A little Validation check in fasterListSort(..) would be great to avoid ArrayoutOfBounds exception. This happens when the second list is empty and the first ain't. Added in this gist:https://gist.github.com/Divyendra/aee1fd1af7f16c8ca9cd. Feel free to merge.