This is an Individual Assignment. You must complete this assignment on your own.

Do not collaborate or share code with other students.

Do not copy and paste code from anywhere.

Especially from Chegg or Course Hero, or Stack Overflow, or from anywhere you found through a Google Search

Students copying or sharing code will be reported to the Dean's office for violating the Academic Integrity Policy and for disciplinary action.

Before you make a serious mistake and risk your grade and enrollment at ASU, please see your instructor for help.

Do not use any resources outside of those provided in the course materials.

Do not use any language features that have not been covered to this point in the course materials.

Do not use any language features that are explicitly forbidden in these instructions.

If you get stuck or need help, please use the help systems provided in this course.

_{Copyright 2021 Arizona State University - This content is protected and may not be shared, uploaded, sold, or distributed in whole or part. Copying any part of these instructions or any part of a solution and sharing online or otherwise in any form is a violation of copyright laws and the ASU Academic Integrity Policy. All violations will be prosecuted.}

Required Skills Inventory

Implement a merge sort algorithm

Implement a recursive algorithm

You are not allowed to use any of the standard Java collection types for this assignment. Do not import any Java standard library features from java.util.

Problem Description and Given Info

For this assignment you are given the following Java source code files:

IList.java (This file is complete make no changes to this file)

MyArrayList.java (This file is complete make no changes to this file)

MySorts.java (You must complete this file)

Main.java (You may use this file to write code to test your quicksort code)

You must complete the public class named MySorts.java with methods as defined below.

Note that your *merge sort algorithm must be implemented to operate on IList objects, as defined in the given files iList.java and MyArrayList.java.

Structure of the MySorts Fields

Your merge sort algorithm should require no static (or instance) fields in your MySorts class.

Structure of the MySorts merge sort Methods

Your MySorts class must implement the following methods:

a public static method named mergesort that takes an object of type IList as an argument and returns nothing

a private static method named mergesortHelper that takes an object of type IList and returns an IList

a private static method named getLeftHalf that takes an object of type IList returns an IList

a private static method named getRightHalf that takes an object of type IList returns an IList

a private static method named merge that takes two IList objects as arguments and returns an IList

You may implement any additional methods that you may need.

Additional Information

MySorts merge sort algorithm

the mergesort method will take a reference to an IList object as its only argument. This method will call the mergesortHelper method to do the actual work of sorting the list. This is the method that one would call to apply the quicksort algorithm to a list of values. By the time this method returns, the values in the argument IList should be sorted.

the mergesortHelper method is a recursive method that will implement the actual merge sort algorithm. The argument is a reference to the list of values that is to be sorted. this method will call the getLeftHalf and getRightHalf methods to divide a larger list, and call the merge method to merge two sorted sub-lists into one sorted list.

the getLeftHalf method will take as its argument, a reference to the list of values that is to be sorted. This method will return an IList that contains the first half of the list that was passed to it as an argument.For examples:

given an IList named list, of these values {1,2,3,4}, getLeftHalf(list) would return an IList with these values {1,2};

given an IList named list, of these values {3,6,2,5,4,1,7}, getLeftHalf(list) would return an IList with these values {3,6,2}

Note that for lists with an odd number of values (like {3,6,2,5,4,1,7}), the getLeftHalf method should return the smaller half of the list (i.e. {3,6,2} instead of {3,6,2,5}).

the getRightHalf method will take as its argument, a reference to the list of values that is to be sorted. This method will return an IList that contains the second half of the list that was passed to it as an argument.For examples:

given an IList named list, of these values {1,2,3,4}, getRightHalf(list) would return an IList with these values {3,4};

given an IList named list, of these values {3,6,2,5,4,1,7}, getRightHalf(list) would return an IList with these values {5,4,1,7}

Note that for lists with an odd number of values (like {3,6,2,5,4,1,7}), the getRightHalf method should return the larger half of the list (i.e. {5,4,1,7} instead of {4,1,7}).

the merge method will take two sorted lists as arguments. This method must create a new IList and merge the two argument lists into one sorted list that will be returned.For examples:

given an IList named list1, of these values {2,4,6}, and an IList named list2, of these values {1,3,5}, merge(list1, list2) would return an IList with these values {1,2,3,4,5,6};

given an IList named list1, of these values {1,4,5,8}, and an IList named list2, of these values {2,3,4,7,9}, merge(list1, list2) would return an IList with these values {1,2,3,4,4,5,7,8,9};

What I got just need to figure out sort function

public class MySorts { public static void mergesort(IList list) { mergesortHelper(list); }

private static IList mergesortHelper(IList list) { if (list.size() <=1){ return list; } if (list.size() == 2){ if (list.get(0) > list.get(1)) { list.set(0, list.get(1)); list.set(1, list.get(0)); } }

IList temp1 = mergesortHelper( getLeftHalf(list) ); IList temp2 = mergesortHelper( getRightHalf(list) );

return merge(temp1, temp2); }

private static IList getLeftHalf(IList list) { int midIndex = list.size()/2; IList newList = new MyArrayList();

for(int i=0; i<= midIndex-1; i++) newList.add(list.get(i));

return newList; }

private static IList getRightHalf(IList list) { int midIndex = list.size()/2; IList newList = new MyArrayList();

for(int i=midIndex; i<= list.size()-1; i++) newList.add(list.get(i));

return newList; }

private static IList merge(IList list1, IList list2) { int ptr1 = 0, ptr2 = 0; IList newList = new MyArrayList();

while(ptr1

while (ptr1 < list1.size()) { newList.add(list1.get(ptr1)); ptr1++; }

while (ptr2 < list2.size()) { newList.add(list2.get(ptr2)); ptr2++; }

return newList; } }