Skip to content

Instantly share code, notes, and snippets.

@netdance
Created January 3, 2014 01:31
Show Gist options
  • Save netdance/8230904 to your computer and use it in GitHub Desktop.
Save netdance/8230904 to your computer and use it in GitHub Desktop.
Various Java methods to create one sorted list from two sorted lists
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);
}
}
@Divyendra
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment