Sorting Algorithm Tutorials - Herong's Tutorial Examples - 6.12, by Herong Yang
Merge Sort - Java Implementation
This section provides a tutorial on how to implement the Merge Sort algorithm in Java.
Here is my Java implementation of Merge Sort algorithm:
/* HyArrays.java * This class contains sorting methods similar to java.util.Arrays.sort(). * All sorting methods should have a signature of * %Sort(Object[] a, int fromIndex, int toIndex) * where "fromIndex" is inclusive, and "toIndex" is exclusive. * Copyright (c) 2011 HerongYang.com. All Rights Reserved. */ public class HyArrays { public static void mergeSort(HyObject[] a, int fromIndex, int toIndex) { HyObject[] b = new HyObject[toIndex]; for (int i=fromIndex; i<toIndex; i++) { b[i] = a[i]; } mergeSortInternal(b, a, fromIndex, toIndex); } private static void mergeSortInternal(HyObject[] a, HyObject[] b, int fromIndex, int toIndex) { if (toIndex-fromIndex<=1) { return; } else if (toIndex-fromIndex==2) { if ((a[fromIndex]).compareTo(a[toIndex-1])>0) { b[toIndex-1] = a[fromIndex]; b[fromIndex] = a[toIndex-1]; } } else { int iMiddle = (toIndex-fromIndex)/2 + fromIndex; mergeSortInternal(b,a,fromIndex,iMiddle); mergeSortInternal(b,a,iMiddle,toIndex); int iLeft = fromIndex; int iRight = iMiddle; int i = fromIndex; while (iLeft<iMiddle && iRight<toIndex) { if ((a[iLeft]).compareTo(a[iRight])>0) { b[i] = a[iRight]; iRight++; } else { b[i] = a[iLeft]; iLeft++; } i++; } while (iLeft<iMiddle) { b[i] = a[iLeft]; iLeft++; i++; } while (iRight<toIndex) { b[i] = a[iRight]; iRight++; i++; } } } }
Note that:
In case you are using older versions of Java that support only the raw "Comparable" interface type, here is my old implementation:
/* HyArrays.java * This class contains sorting methods similar to java.util.Arrays. * All sorting methods should have a signature of * %Sort(Object[] a, int fromIndex, int toIndex) * where "fromIndex" is inclusive, and "toIndex" is exclusive. * Copyright (c) 2011 HerongYang.com. All Rights Reserved. */ public class HyArrays { public static void mergeSort(Object[] a, int fromIndex, int toIndex) { Object[] b = new Object[toIndex]; for (int i=fromIndex; i<toIndex; i++) { b[i] = a[i]; } mergeSortInternal(b, a, fromIndex, toIndex); } private static void mergeSortInternal(Object[] a, Object[] b, int fromIndex, int toIndex) { if (toIndex-fromIndex<=1) { return; } else if (toIndex-fromIndex==2) { if (((Comparable)a[fromIndex]).compareTo(a[toIndex-1])>0) { b[toIndex-1] = a[fromIndex]; b[fromIndex] = a[toIndex-1]; } } else { int iMiddle = (toIndex-fromIndex)/2 + fromIndex; mergeSortInternal(b,a,fromIndex,iMiddle); mergeSortInternal(b,a,iMiddle,toIndex); int iLeft = fromIndex; int iRight = iMiddle; int i = fromIndex; while (iLeft<iMiddle && iRight<toIndex) { if (((Comparable)a[iLeft]).compareTo(a[iRight])>0) { b[i] = a[iRight]; iRight++; } else { b[i] = a[iLeft]; iLeft++; } i++; } while (iLeft<iMiddle) { b[i] = a[iLeft]; iLeft++; i++; } while (iRight<toIndex) { b[i] = a[iRight]; iRight++; i++; } } } }
Table of Contents
Introduction of Sorting Algorithms
Java API for Sorting Algorithms
Insertion Sort Algorithm and Java Implementation
Selection Sort Algorithm and Java Implementation
Bubble Sort Algorithm and Java Implementation
Quicksort Algorithm and Java Implementation
►Merge Sort Algorithm and Java Implementation
Merge Sort - Algorithm Introduction
►Merge Sort - Java Implementation
Merge Sort - Implementation Improvements
Heap Sort Algorithm and Java Implementation
Shell Sort Algorithm and Java Implementation
Sorting Algorithms Implementations in PHP
Sorting Algorithms Implementations in Perl
Sorting Algorithms Implementations in Python