Java Merge Sort Implementation

Merge sort works by divide the unsorted list into N sublists, where N is the number of elements in the list. This gives us N lists and each of them only contain one element. One element is always sorted, thus we have N sorted lists. Now with the N sorted lists, we repeatedly merge them to produce new sublists until there is only 1 list remaining and that will be the sorted list.

The mergeSort method, takes in a list of N elements, divide it into N lists, them merge them back with a sorted list.
[code language=”java”]
public ArrayList<String> mergeSort(ArrayList<String> whole) {
ArrayList<String> left = new ArrayList<String>();
ArrayList<String> right = new ArrayList<String>();
int center;

if (whole.size() == 1) {
return whole;
} else {
center = whole.size()/2;
// copy the left half of whole into the left.
for (int i=0; i<center; i++) {
left.add(whole.get(i));
}

//copy the right half of whole into the new arraylist.
for (int i=center; i<whole.size(); i++) {
right.add(whole.get(i));
}

// Sort the left and right halves of the arraylist.
left = mergeSort(left);
right = mergeSort(right);

// Merge the results back together.
merge(left, right, whole);
}
return whole;
}
[/code]

The merge method for merging the N sublists into a sorted list.
[code language=”java”]
private void merge(ArrayList<String> left, ArrayList<String> right, ArrayList<String> whole) {
int leftIndex = 0;
int rightIndex = 0;
int wholeIndex = 0;

// As long as neither the left nor the right ArrayList has
// been used up, keep taking the smaller of left.get(leftIndex)
// or right.get(rightIndex) and adding it at both.get(bothIndex).
while (leftIndex < left.size() && rightIndex < right.size()) {
if ( (left.get(leftIndex).compareTo(right.get(rightIndex))) < 0) {
whole.set(wholeIndex, left.get(leftIndex));
leftIndex++;
} else {
whole.set(wholeIndex, right.get(rightIndex));
rightIndex++;
}
wholeIndex++;
}

ArrayList<String> rest;
int restIndex;
if (leftIndex >= left.size()) {
// The left ArrayList has been use up…
rest = right;
restIndex = rightIndex;
} else {
// The right ArrayList has been used up…
rest = left;
restIndex = leftIndex;
}

// Copy the rest of whichever ArrayList (left or right) was not used up.
for (int i=restIndex; i<rest.size(); i++) {
whole.set(wholeIndex, rest.get(i));
wholeIndex++;
}
}
[/code]

Merge sort complete example in a Java class.
[code language=”java”]
import java.util.ArrayList;
import java.util.Scanner;
public class MergeSort {

private ArrayList<String> strList;

// Constructor
public MergeSort(ArrayList<String> input) {
strList = input;
}

public void sort() {
strList = mergeSort(strList);
}

public ArrayList<String> mergeSort(ArrayList<String> whole) {
ArrayList<String> left = new ArrayList<String>();
ArrayList<String> right = new ArrayList<String>();
int center;

if (whole.size() == 1) {
return whole;
} else {
center = whole.size()/2;
// copy the left half of whole into the left.
for (int i=0; i<center; i++) {
left.add(whole.get(i));
}

//copy the right half of whole into the new arraylist.
for (int i=center; i<whole.size(); i++) {
right.add(whole.get(i));
}

// Sort the left and right halves of the arraylist.
left = mergeSort(left);
right = mergeSort(right);

// Merge the results back together.
merge(left, right, whole);
}
return whole;
}

private void merge(ArrayList<String> left, ArrayList<String> right, ArrayList<String> whole) {
int leftIndex = 0;
int rightIndex = 0;
int wholeIndex = 0;

// Copy the rest of whichever ArrayList (left or right) was not used up.
for (int i=restIndex; i<rest.size(); i++) {
whole.set(wholeIndex, rest.get(i));
wholeIndex++;
}
}

public void show() {
System.out.println("Sorted:");
for (int i=0; i< strList.size();i++) {
System.out.println(strList.get(i));
}
}

public static void main(String[] args) {
ArrayList<String> input = new ArrayList<String>();
Scanner sc = new Scanner(System.in);

System.out.println("Enter your text, type done for exit:");
String strin = sc.nextLine();

while(!strin.equals("done")) {
input.add(strin);
strin = sc.nextLine();
}
System.out.println("************************");
MergeSort test = new MergeSort(input);
test.sort();
test.show();
}
}
[/code]

The output:

See Insertion Sort, Bubble Sort and other Sortings

Search within Codexpedia

Custom Search

Search the entire web

Custom Search