Last active
August 29, 2015 14:23
-
-
Save snarkbait/7d65d2cb4fcc4ab8b0d3 to your computer and use it in GitHub Desktop.
Top-Down Merge Sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Generic Top-Down Merge Sort | |
* Based on this | |
* https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists | |
* | |
* for http://www.reddit.com/r/javaexamples | |
* by user /u/Philboyd_Studge | |
* | |
* PUBLIC LICENSE - This software is released with an unlimited license. | |
* There is no specification of any kind on its usage or implementation. | |
* The Author has no bounds or restrictions on its use. Crumple it up and throw it | |
* at a ceiling fan if you would like!! Besides, nobody reads these things, like ever. | |
* I could literally just be quoting lorem ipsum here because anyone would just scroll past | |
* the commented-out code and go to the actual code. Instead I will throw some more official- | |
* sounding words out there - IN ACCORDANCE WITH GALACTIC PRINCIPLES ~107.4B THIS SOFTWARE | |
* HAS A REASONABLE EXPECTATION OF BECOMING SELF-AWARE AND POSSIBLY ATTEMPTING TO SCOUR THE | |
* EARTH, ERADICATING ALL HUMAN LIFE. PLEASE USE WITH CAUTION. | |
*/ | |
import java.util.List; | |
import java.util.ArrayList; | |
import java.util.NoSuchElementException; | |
/** | |
* Generic, Top-Down Merge Sort | |
* Static methods for merge sorting a List of Comparable types. | |
* Usage <code>List<Type> sorted = MergeSort.mergeSort(listToSort);</code> | |
* Based on <a href ="https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists">This wikipedia entry</a> | |
* @author /u/Philboyd_Studge | |
*/ | |
public class MergeSort | |
{ | |
/** | |
* recursive mergeSort() | |
* @param List of Comparable type T | |
* @return sorted List of Comparable type T | |
*/ | |
public static <T extends Comparable<T>> List<T> mergeSort(List<T> m) | |
{ | |
// exception | |
if (m==null) throw new NoSuchElementException("List is null"); | |
// base case | |
if (m.size() <= 1) return m; | |
// make lists | |
List<T> left = new ArrayList<>(); | |
List<T> right = new ArrayList<>(); | |
// get middle | |
int middle = m.size()/2; | |
// fill left list | |
for (int i = 0; i < middle; i++) | |
{ | |
if (m.get(i)!=null) left.add(m.get(i)); | |
} | |
// fill right list | |
for (int i = middle; i < m.size(); i++) | |
{ | |
if (m.get(i)!=null) right.add(m.get(i)); | |
} | |
// recurse | |
left = mergeSort(left); | |
right = mergeSort(right); | |
// merge | |
return merge(left,right); | |
} | |
/** | |
* private merge() method used in mergeSort() | |
* @param left List of type T | |
* @param right List of type T | |
* @return result List of type T | |
*/ | |
private static <T extends Comparable<T>> List<T> merge(List<T> left, List<T> right) | |
{ | |
List<T> result = new ArrayList<>(); | |
// merge | |
while (!left.isEmpty() && !right.isEmpty()) | |
{ | |
if (left.get(0).compareTo(right.get(0)) <= 0) | |
{ | |
result.add(left.remove(0)); | |
} | |
else | |
{ | |
result.add(right.remove(0)); | |
} | |
} | |
// cleanup leftovers | |
while (!left.isEmpty()) | |
{ | |
result.add(left.remove(0)); | |
} | |
while (!right.isEmpty()) | |
{ | |
result.add(right.remove(0)); | |
} | |
return result; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Unsorted array | |
[233, 307, 0, 780, 413, 386, 525, 213, 651, 454, 71, 252, 570, 745, 775, 994, 150, 757, 358, 323, 72 | |
0, 756, 325, 55, 877, 801, 513, 171, 795, 215, 382, 22, 216, 5, 540, 411, 325, 698, 639, 691, 336, 9 | |
62, 688, 540, 375, 621, 473, 777, 704, 520, 678, 295, 190, 259, 151, 938, 821, 622, 106, 578, 366, 6 | |
73, 973, 405, 879, 694, 681, 858, 794, 181, 338, 615, 821, 460, 963, 320, 849, 849, 318, 493, 668, 5 | |
25, 473, 462, 650, 655, 844, 597, 400, 386, 15, 705, 449, 164, 161, 994, 81, 812, 906, 78] | |
Sorted List | |
0, 5, 15, 22, 55, 71, 78, 81, 106, 150, 151, 161, 164, 171, 181, 190, 213, 215, 216, 233, 252, 259, | |
295, 307, 318, 320, 323, 325, 325, 336, 338, 358, 366, 375, 382, 386, 386, 400, 405, 411, 413, 449, | |
454, 460, 462, 473, 473, 493, 513, 520, 525, 525, 540, 540, 570, 578, 597, 615, 621, 622, 639, 650, | |
651, 655, 668, 673, 678, 681, 688, 691, 694, 698, 704, 705, 720, 745, 756, 757, 775, 777, 780, 794, | |
795, 801, 812, 821, 821, 844, 849, 849, 858, 877, 879, 906, 938, 962, 963, 973, 994, 994 | |
Abed | |
Annie | |
Britta | |
Chang | |
Dean | |
Jeff | |
Pierce | |
Shirley | |
Troy |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
import java.util.Random; | |
import java.util.List; | |
class TestMergeSort | |
{ | |
public static void main(String[] args) | |
{ | |
Integer[] numbers = new Integer[100]; | |
Random rand = new Random(); | |
for (int i = 0; i < numbers.length; i++) | |
{ | |
numbers[i] = rand.nextInt(1000); | |
} | |
System.out.println("Unsorted array"); | |
System.out.println(Arrays.toString(numbers)); | |
List<Integer> result = MergeSort.mergeSort(Arrays.asList(numbers)); | |
System.out.println("Sorted List"); | |
for(Integer each : result) System.out.print(each + ", "); | |
System.out.println(); | |
// test Strings | |
String[] names = { "Pierce", "Chang", "Britta", "Abed", "Dean", "Jeff", "Shirley", "Annie", "Troy"} ; | |
for (String each: MergeSort.mergeSort(Arrays.asList(names))) | |
System.out.println(each); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment