Suppose that you have a function merge

(merge (list 1 3 5) (list 2 4 4 7 9)) --> (list 1 2 3 4 4 5 7 9)

Define a suitable merge in Java. 

Assume you have it. Define a suitable sort using it. 

To clarify here's how sort should work:

(sort (list 1 4 3 5 2 2 4)) -> 

(sort '((1) (4) (3) (5) (2) (2) (4))) -> 

(sort '((3) (5) (2) (2) (4) (merge '((1) (4))))) -> 

(sort '( (2) (2) (4) (1 4) (3 5) )) -> 

(sort '( (4) (1 4) (3 5) (2 2) )) -> 

(sort '( (3 5) (2 2) (1 4 4) )) -> 

(sort '( (1 4 4) (2 2 3 5) )) -> 

(sort '( (1 2 2 3 4 4 5) )) -> 

'( (1 2 2 3 4 4 5) )) 
 
Can you define a suitable sort (as shown above) in Java? 

Microsoft Windows [Version 10.0.14393]
(c) 2016 Microsoft Corporation. All rights reserved.

C:\WINDOWS\system32>cd \

C:\>cd Users

C:\Users>cd dgerman

C:\Users\dgerman>cd Desktop

C:\Users\dgerman\Desktop>PATH="C:\Program Files\Java\jdk1.8.0_144\bin";%PATH%

C:\Users\dgerman\Desktop>javac
Usage: javac <options> <source files>
where possible options include:
  -g                         Generate all debugging info
  -g:none                    Generate no debugging info
  -g:{lines,vars,source}     Generate only some debugging info
  -nowarn                    Generate no warnings
  -verbose                   Output messages about what the compiler is doing
  -deprecation               Output source locations where deprecated APIs are used
  -classpath <path>          Specify where to find user class files and annotation processors
  -cp <path>                 Specify where to find user class files and annotation processors
  -sourcepath <path>         Specify where to find input source files
  -bootclasspath <path>      Override location of bootstrap class files
  -extdirs <dirs>            Override location of installed extensions
  -endorseddirs <dirs>       Override location of endorsed standards path
  -proc:{none,only}          Control whether annotation processing and/or compilation is done.
  -processor <class1>[,<class2>,<class3>...] Names of the annotation processors to run; bypasses default discovery process
  -processorpath <path>      Specify where to find annotation processors
  -parameters                Generate metadata for reflection on method parameters
  -d <directory>             Specify where to place generated class files
  -s <directory>             Specify where to place generated source files
  -h <directory>             Specify where to place generated native header files
  -implicit:{none,class}     Specify whether or not to generate class files for implicitly referenced files
  -encoding <encoding>       Specify character encoding used by source files
  -source <release>          Provide source compatibility with specified release
  -target <release>          Generate class files for specific VM version
  -profile <profile>         Check that API used is available in the specified profile
  -version                   Version information
  -help                      Print a synopsis of standard options
  -Akey[=value]              Options to pass to annotation processors
  -X                         Print a synopsis of nonstandard options
  -J<flag>                   Pass <flag> directly to the runtime system
  -Werror                    Terminate compilation if warnings occur
  @<filename>                Read options and filenames from file


C:\Users\dgerman\Desktop>java
Usage: java [-options] class [args...]
           (to execute a class)
   or  java [-options] -jar jarfile [args...]
           (to execute a jar file)
where options include:
    -d32          use a 32-bit data model if available
    -d64          use a 64-bit data model if available
    -server       to select the "server" VM
                  The default VM is server.

    -cp <class search path of directories and zip/jar files>
    -classpath <class search path of directories and zip/jar files>
                  A ; separated list of directories, JAR archives,
                  and ZIP archives to search for class files.
    -D<name>=<value>
                  set a system property
    -verbose:[class|gc|jni]
                  enable verbose output
    -version      print product version and exit
    -version:<value>
                  Warning: this feature is deprecated and will be removed
                  in a future release.
                  require the specified version to run
    -showversion  print product version and continue
    -jre-restrict-search | -no-jre-restrict-search
                  Warning: this feature is deprecated and will be removed
                  in a future release.
                  include/exclude user private JREs in the version search
    -? -help      print this help message
    -X            print help on non-standard options
    -ea[:<packagename>...|:<classname>]
    -enableassertions[:<packagename>...|:<classname>]
                  enable assertions with specified granularity
    -da[:<packagename>...|:<classname>]
    -disableassertions[:<packagename>...|:<classname>]
                  disable assertions with specified granularity
    -esa | -enablesystemassertions
                  enable system assertions
    -dsa | -disablesystemassertions
                  disable system assertions
    -agentlib:<libname>[=<options>]
                  load native agent library <libname>, e.g. -agentlib:hprof
                  see also, -agentlib:jdwp=help and -agentlib:hprof=help
    -agentpath:<pathname>[=<options>]
                  load native agent library by full pathname
    -javaagent:<jarpath>[=<options>]
                  load Java programming language agent, see java.lang.instrument
    -splash:<imagepath>
                  show splash screen with specified image
See http://www.oracle.com/technetwork/java/javase/documentation/index.html for more details.

C:\Users\dgerman\Desktop>

import java.util.ArrayList; 

public class Wednesday {
  public static void main(String[] args) {
    ArrayList<Integer> a = new ArrayList<Integer>(); 
    for (String number : args) {
      a.add( Integer.parseInt( number ) ); 
    }
    System.out.println( a ); 
    ArrayList<Integer> b = Wednesday.sort( a ); 
    System.out.println( b ); 
    
  }
  public static ArrayList<Integer> sort(ArrayList<Integer> input) {

    return null; 
  } 
}

Let's write some more.

import java.util.ArrayList; 

public class Wednesday {
  public static void main(String[] args) {
    ArrayList<Integer> a = new ArrayList<Integer>(); 
    for (String number : args) {
      a.add( Integer.parseInt( number ) ); 
    }
    System.out.println( a ); 
    ArrayList<Integer> b = Wednesday.sort( a ); 
    System.out.println( b ); 
    
  }
  public static ArrayList<Integer> sort(ArrayList<Integer> input) {
    ArrayList<ArrayList<Integer>> result; 
    result = new ArrayList<ArrayList<Integer>>(); 
    for (Integer number : input) {
      ArrayList<Integer> bag = new ArrayList<Integer>(); 
      bag.add( number ); 
      result.add(bag); 
    } 

    System.out.println( result );
    return result.get(0); 
  } 
}

What is our next step? 

import java.util.ArrayList; 

public class Wednesday {
  public static void main(String[] args) {
    ArrayList<Integer> a = new ArrayList<Integer>(); 
    for (String number : args) {
      a.add( Integer.parseInt( number ) ); 
    }
    System.out.println( a ); 
    ArrayList<Integer> b = Wednesday.sort( a ); 
    System.out.println( b ); 
    
  }
  public static ArrayList<Integer> sort(ArrayList<Integer> input) {
    ArrayList<ArrayList<Integer>> result; 
    result = new ArrayList<ArrayList<Integer>>(); 
    for (Integer number : input) {
      ArrayList<Integer> bag = new ArrayList<Integer>(); 
      bag.add( number ); 
      result.add(bag); 
    } 
    while (result.size() > 1) {
      System.out.println( result ); 
      ArrayList<Integer> a = result.get(0); 
      ArrayList<Integer> b = result.get(1); 
      ArrayList<Integer> m = Wednesday.merge(a, b); 
      result.add(m); 
      result.remove(0); 
      result.remove(0); 
    }
    System.out.println( result );
    return result.get(0); 
  } 
  public static ArrayList<Integer> merge(ArrayList<Integer> a, 
                                         ArrayList<Integer> b) {
    return a;
  } 
}

Now all I have to do is to finish merge.

import java.util.ArrayList; 

public class Wednesday {
  public static void main(String[] args) {
    if( args.length == 0) {
      System.out.println("[ ]");
      System.exit(0); 
    } 
    ArrayList<Integer> a = new ArrayList<Integer>(); 
    for (String number : args) {
      a.add( Integer.parseInt( number ) ); 
    }
    System.out.println( a ); 
    ArrayList<Integer> b = Wednesday.sort( a ); 
    System.out.println( b ); 
    
  }
  public static ArrayList<Integer> sort(ArrayList<Integer> input) {
    ArrayList<ArrayList<Integer>> result; 
    result = new ArrayList<ArrayList<Integer>>(); 
    for (Integer number : input) {
      ArrayList<Integer> bag = new ArrayList<Integer>(); 
      bag.add( number ); 
      result.add(bag); 
    } 
    while (result.size() > 1) {
      System.out.println( result ); 
      ArrayList<Integer> a = result.get(0); 
      ArrayList<Integer> b = result.get(1); 
      ArrayList<Integer> m = Wednesday.merge(a, b); 
      result.add(m); 
      result.remove(0); 
      result.remove(0); 
    }
    System.out.println( result );
    return result.get(0); 
  } 
  public static ArrayList<Integer> merge(ArrayList<Integer> a, 
                                         ArrayList<Integer> b) {
    ArrayList<Integer> result = new ArrayList<Integer>(); 
    while (a.size() > 0 || b.size() > 0) {
      if (a.size() == 0) {
        result.add( b.get(0) ); 
        b.remove(0); 
        // continue; 
      } else if (b.size() == 0) {
        result.add( a.get(0) ); 
        a.remove(0); 
        // continue; 
      } else {
        if (a.get(0) < b.get(0)) {
          result.add( a.get(0) ); 
          a.remove(0); 
          // continue; 
        } else {
          result.add( b.get(0) ); 
          b.remove(0); 
          // continue; 
        } 
      }  
    }
    return result; 
  } 
}

How does this work?

C:\Users\dgerman\Desktop>javac Wednesday.java

C:\Users\dgerman\Desktop>java Wednesday 3 2 4 5 1
[3, 2, 4, 5, 1]
[[3], [2], [4], [5], [1]]
[[4], [5], [1], [2, 3]]
[[1], [2, 3], [4, 5]]
[[4, 5], [1, 2, 3]]
[[1, 2, 3, 4, 5]]
[1, 2, 3, 4, 5]

C:\Users\dgerman\Desktop>

We need to automate this. See you next time. 

--

Final version of the code:

import java.util.ArrayList; 

public class Wednesday {
  public static void main(String[] args) {
    if( args.length == 0) {
      System.out.println("[ ]");
      System.exit(0); 
    } 
    ArrayList<Integer> a = new ArrayList<Integer>(); 
    for (String number : args) {
      a.add( Integer.parseInt( number ) ); 
    }
    System.out.println( a ); 
    ArrayList<Integer> b = Wednesday.sort( a ); 
    System.out.println( b ); 
    
  }
  public static ArrayList<Integer> sort(ArrayList<Integer> input) {
    ArrayList<ArrayList<Integer>> result; 
    result = new ArrayList<ArrayList<Integer>>(); 
    for (Integer number : input) {
      ArrayList<Integer> bag = new ArrayList<Integer>(); 
      bag.add( number ); 
      result.add(bag); 
    } 
    while (result.size() > 1) {
      System.out.println( result ); 
      ArrayList<Integer> a = result.get(0); 
      ArrayList<Integer> b = result.get(1); 
      ArrayList<Integer> m = Wednesday.merge(a, b); 
      result.add(m); 
      result.remove(0); 
      result.remove(0); 
    }
    System.out.println( result );
    return result.get(0); 
  } 
  public static ArrayList<Integer> merge(ArrayList<Integer> a, 
                                         ArrayList<Integer> b) {
    ArrayList<Integer> result = new ArrayList<Integer>(); 
    while (a.size() > 0 || b.size() > 0) {
      // System.out.println( result ); 
      if (a.size() == 0) {
        result.add( b.get(0) ); 
        b.remove(0); 
        // continue; 
      } else if (b.size() == 0) {
        result.add( a.get(0) ); 
        a.remove(0); 
        // continue; 
      } else {
        if (a.get(0) < b.get(0)) {
          result.add( a.get(0) ); 
          a.remove(0); 
          // continue; 
        } else {
          result.add( b.get(0) ); 
          b.remove(0); 
          // continue; 
        } 
      }  
    }
    // System.out.println("----------------"); 
    return result; 
  } 
}

See you in lab!