The algorithm for sorting primitive types in Java is a variant of 3-way quicksort developed by Bentley and McIlroy. It is extremely efficient for most inputs that arise in practice, including inputs that are already sorted. However, using a clever technique described by

M. D. McIlroy in A Killer Adversary for Quicksort (https://www.cs.dartmouth.edu/~doug/mdmspe.pdf),

it is possible to construct pathological inputs that make the system sort run in quadratic time. Even worse, it is blows the function call stack. To see Java's sorting library break, here are some pathological inputs of varying sizes:

10,000 (https://algs4.cs.princeton.edu/23quicksort/antiquicksort10K.txt)

20,000 (https://algs4.cs.princeton.edu/23quicksort/antiquicksort20K.txt)

50,000 (https://algs4.cs.princeton.edu/23quicksort/antiquicksort50K.txt)

100,000 (https://algs4.cs.princeton.edu/23quicksort/antiquicksort100K.txt)

250,000 (https://algs4.cs.princeton.edu/23quicksort/antiquicksort250K.txt)

500,000 (https://algs4.cs.princeton.edu/23quicksort/antiquicksort500K.txt)

1,000,000. (https://algs4.cs.princeton.edu/23quicksort/antiquicksort1M.txt) Test them out using the program IntegerSort.java which takes a command line input N, reads in N integers from standard input, and sorts them using the system sort.

Submit:

Screenshots of 4 different outputs using 4 of the "pathological inputs" listed above

1 paragraph explanation of the results with a quoted reference from A Killer Adversary for Quicksort

and another quoted reference from an online source on "pathological inputs" for Quicksort

/****************************************************************************** * Compilation: javac IntegerSort.java * Execution: java IntegerSort < input.txt * * Reads in sequence of integers between 0 and 99 and print them in * sorted order. * * % more input.txt * 98 2 3 1 0 0 0 3 98 98 2 2 2 0 0 0 2 * * % java IntegerSort < input.txt * 0 0 0 0 0 0 1 2 2 2 2 2 3 3 98 98 98 * ******************************************************************************/ public class IntegerSort { public static void main(String[] args) { int MAX = 100; // integers are between 0 and MAX-1 int[] freq = new int[MAX]; // freq[i] = number of occurrences of i // read in values and calculate frequencies while (!StdIn.isEmpty()) { int i = StdIn.readInt(); if (i < 0 || i >= MAX) throw new RuntimeException("Invalid integer"); freq[i]++; } // print values in sorted order for (int i = 0; i < MAX; i++) { for (int j = 0; j < freq[i]; j++) { StdOut.print(i + " "); } } StdOut.println(); } }