Course navigation & on this page
Merge sort
Recursively sort two halves and merge their ordered elements.
Overview
Recursively sort two halves and merge their ordered elements. The standard supplied top-down version does Θ(n) merge work at each of Θ(log n) levels. Its auxiliary array dominates the logarithmic call stack.
Step-by-step walkthrough
- Stop at a subarray of size zero or one.
- Recursively sort each half.
- Copy the relevant range to the auxiliary array.
- Take the smaller available element from the two halves.
Complexity analysis
| Best case | Θ(n log n) |
|---|---|
| Average / aggregate | Θ(n log n) |
| Worst case | Θ(n log n) |
| Space | Θ(n) auxiliary |
The standard supplied top-down version does Θ(n) merge work at each of Θ(log n) levels. Its auxiliary array dominates the logarithmic call stack.
A worked example
[5,3,8,1] splits to [5,3] and [8,1]; sorted halves [3,5] and [1,8] merge to [1,3,5,8].
Common mistake / implementation note
Preserving stability requires taking from the left half first when keys compare equal.
Preserving stability requires taking from the left half first when keys compare equal.
Original course code
Source: algs4/Merge.java. Original logic, comments, variable names and attribution are retained.
Download Merge.javaMerge.javaJAVA
/****************************************************************************** * Compilation: javac Merge.java * Execution: java Merge < input.txt * Dependencies: StdOut.java StdIn.java * Data files: https://algs4.cs.princeton.edu/22mergesort/tiny.txt * https://algs4.cs.princeton.edu/22mergesort/words3.txt * * Sorts a sequence of strings from standard input using mergesort. * * % more tiny.txt * S O R T E X A M P L E * * % java Merge < tiny.txt * A E E L M O P R S T X [ one string per line ] * * % more words3.txt * bed bug dad yes zoo ... all bad yet * * % java Merge < words3.txt * all bad bed bug dad ... yes yet zoo [ one string per line ] * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code Merge} class provides static methods for sorting an * array using a top-down, recursive version of <em>mergesort</em>. * <p> * This implementation takes Θ(<em>n</em> log <em>n</em>) time * to sort any array of length <em>n</em> (assuming comparisons * take constant time). It makes between * ~ ½ <em>n</em> log<sub>2</sub> <em>n</em> and * ~ 1 <em>n</em> log<sub>2</sub> <em>n</em> compares. * <p> * This sorting algorithm is stable. * It uses Θ(<em>n</em>) extra memory (not including the input array). * <p> * For additional documentation, see * <a href="https://algs4.cs.princeton.edu/22mergesort">Section 2.2</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * For an optimized version, see {@link MergeX}. * * @author Robert Sedgewick * @author Kevin Wayne */public class Merge { // This class should not be instantiated. private Merge() { } // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi] private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays assert isSorted(a, lo, mid); assert isSorted(a, mid+1, hi); // copy to aux[] for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } // postcondition: a[lo .. hi] is sorted assert isSorted(a, lo, hi); } // mergesort a[lo..hi] using auxiliary array aux[lo..hi] private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid + 1, hi); merge(a, aux, lo, mid, hi); } /** * Rearranges the array in ascending order, using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { Comparable[] aux = new Comparable[a.length]; sort(a, aux, 0, a.length-1); assert isSorted(a); } /*************************************************************************** * Helper sorting function. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } /*************************************************************************** * Check if array is sorted - useful for debugging. ***************************************************************************/ private static boolean isSorted(Comparable[] a) { return isSorted(a, 0, a.length - 1); } private static boolean isSorted(Comparable[] a, int lo, int hi) { for (int i = lo + 1; i <= hi; i++) if (less(a[i], a[i-1])) return false; return true; } /*************************************************************************** * Index mergesort. ***************************************************************************/ // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi] private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) { // copy to aux[] for (int k = lo; k <= hi; k++) { aux[k] = index[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) index[k] = aux[j++]; else if (j > hi) index[k] = aux[i++]; else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++]; else index[k] = aux[i++]; } } /** * Returns a permutation that gives the elements in the array in ascending order. * @param a the array * @return a permutation {@code p[]} such that {@code a[p[0]]}, {@code a[p[1]]}, * ..., {@code a[p[N-1]]} are in ascending order */ public static int[] indexSort(Comparable[] a) { int n = a.length; int[] index = new int[n]; for (int i = 0; i < n; i++) index[i] = i; int[] aux = new int[n]; sort(a, index, aux, 0, n-1); return index; } // mergesort a[lo..hi] using auxiliary array aux[lo..hi] private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, index, aux, lo, mid); sort(a, index, aux, mid + 1, hi); merge(a, index, aux, lo, mid, hi); } // print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } } /** * Reads in a sequence of strings from standard input; mergesorts them; * and prints them to standard output in ascending order. * * @param args the command-line arguments */ public static void main(String[] args) { String[] a = StdIn.readAllStrings(); Merge.sort(a); show(a); }} /****************************************************************************** * Copyright 2002-2020, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/