Merge Sort Algorithm Java
(Merge sort algorithm video tutorial)
Slowly building my list of algorithm implementation, this time it’s Merge sort algorithm. Let me know if you found error on my code. 🙂
Merge Sort Algorithm Pseudo code
from “Merge sort” Wikipedia.
[javascript]
function merge_sort(list m)
// if list size is 1, consider it sorted and return it
if length(m) <= 1
return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after or equal middle
add x to right
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)
function merge(left, right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) <= first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result
[/javascript]
Merge Sort Algorithm Java code
Download the code from GitHub.
[java]
import java.util.Arrays;
import java.util.Random;
/**
* Merge sort algorithm (Top down)
* based on pseudocode at Wikipedia “Merge sort” article
* @see
* @author djitz
*
*/
public class MergeSort {
/**
* Main method.
* @param args
*/
public static void main(String[] args) {
MergeSort app = new MergeSort();
//Generate an integer array of length 7
int[] input = app.generateRandomNumbers(7);
//Before sort
System.out.println(Arrays.toString(input));
//After sort
System.out.println(Arrays.toString(app.mergeSort(input)));
}
/**
* This method sort the input array using top-down
* merge sort algorithm.
* @param input the array of integers to sort.
* @return sorted array of integers.
*/
private int[] mergeSort(int[] input){
if(input.length == 1){
return input;
}
int middle = (int) Math.ceil((double)input.length / 2);
int[] left = new int[middle];
int rightLength = 0;
if(input.length % 2 == 0){
rightLength = middle;
}
else{
rightLength = middle – 1;
}
int[] right = new int[rightLength];
int leftIndex = 0;
int rightIndex = 0;
for (int i = 0; i < input.length; i++) { if(i < middle){ left[leftIndex] = input[i]; leftIndex++; } else{ right[rightIndex] = input[i]; rightIndex++; } } left = mergeSort(left); right = mergeSort(right); return merge(left, right); } /** * This method merge two integer arrays into a sorted integer array. * @param left first array. * @param right second array. * @return a sorted integer array. */ private int[] merge(int[] left, int[] right){ int[] result = new int[left.length + right.length]; int leftIndex = 0; int rightIndex = 0; int resultIndex = 0; while(leftIndex < left.length || rightIndex < right.length){ if(leftIndex < left.length && rightIndex < right.length){ if(left[leftIndex] < right[rightIndex]){ result[resultIndex] = left[leftIndex]; leftIndex++; resultIndex++; } else{ result[resultIndex] = right[rightIndex]; rightIndex++; resultIndex++; } } else if(leftIndex < left.length){ for (int i = resultIndex; i < result.length; i++) { result[i] = left[leftIndex]; leftIndex++; } } else if(rightIndex < right.length){ for (int i = resultIndex; i < result.length; i++) { result[i] = right[rightIndex]; rightIndex++; } } } return result; } /** * This method generate array of random integers with length n. * @param n the length of the array to generate. * @return array of random integers with length n. */ private int[] generateRandomNumbers(int n){ int[] result = new int[n]; Random random = new Random(); for (int i = 0; i < result.length; i++) { result[i] = random.nextInt(n * 10); } return result; } } [/java]