``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 ``` ```package algs22; import stdlib.*; // PROBLEM 2.2.17 public class MyLinkedSort { static class Node { public Node() { } public double item; public Node next; } int N; Node first; private void sort() { // TODO } public MyLinkedSort () { first = null; N = 0; checkInvariants (); } private void myassert (String s, boolean b) { if (!b) throw new Error ("Assertion failed: " + s); } private void checkInvariants() { myassert("Empty <==> first==null", (N == 0) == (first == null)); Node x = first; for (int i = 0; i < N; i++) { if (x==null) { throw new Error ("List too short!"); } x = x.next; } myassert("EndOfList == null", x == null); } public boolean isEmpty () { return first == null; } public int size () { return N; } public void add (double item) { Node newfirst = new Node (); newfirst.item = item; newfirst.next = first; first = newfirst; N++; } private static void print (String s, MyLinkedSort b) { StdOut.print (s + ": "); for (Node x = b.first; x != null; x = x.next) StdOut.print (x.item + " "); StdOut.println (); } private static void print (String s, MyLinkedSort b, double i) { StdOut.print (s + ": "); for (Node x = b.first; x != null; x = x.next) StdOut.print (x.item + " "); StdOut.println (": " + i); } public static void main (String args[]) { int[] a1 = new int[20]; for (int i = 0; i < a1.length; i++) a1[i] = i; StdRandom.shuffle (a1); MyLinkedSort b1 = new MyLinkedSort (); for (int i:a1) b1.add(i); MyLinkedSort.print("before sort",b1); b1.sort(); MyLinkedSort.print("after sort",b1); int[] a2 = new int[200]; for (int i = 0; i < a2.length; i++) a2[i] = i; StdRandom.shuffle (a2); MyLinkedSort b2 = new MyLinkedSort (); for (int i:a1) b2.add(i); MyLinkedSort.print("before sort",b2); b2.sort(); MyLinkedSort.print("after sort",b2); } } ```