Implement a method called bubbleSort, that takes an ArrayList, sorts it using bubble sort algorithm, and returns a sorted list; 2. Implement a method called selectionSort, that takes an ArrayList, sorts it using selection sort algorithm, and returns a sorted list; 3. Implement a method called insertionSort, that takes an ArrayList, sorts it using insertion sort algorithm, and returns a sorted list; 4. Implement a method called mergeSort, that takes an ArrayList, sorts it using merge sort algorithm, and returns a sorted list.

Java algorithm is given below

Explanation:

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Random;

public class Temp {

   static void bubbleSort(ArrayList<Integer> list) {

       int n = list.size();

       for (int p = 0; p < n - 1; p++)

           for (int q = 0; q < n - p - 1; q++)

               if (list.get(q) > list.get(q + 1)) {

                   int temp = list.get(q);

                   list.set(q, list.get(q + 1));

                   list.set(q + 1, temp);

               }

   }

   static void selectionSort(ArrayList<Integer> list) {

       int n = list.size();

       for (int p = 0; p < n - 1; p++) {

           int minimumIndex = p;

           for (int q = p + 1; q < n; q++)

               if (list.get(q) < list.get(minimumIndex))

                   minimumIndex = q;

           int temp = list.get(p);

           list.set(p, list.get(minimumIndex));

           list.set(minimumIndex, temp);

       }

   }

   static void insertionSort(ArrayList<Integer> list) {

       int size = list.size();

       int p, val, q;

       for (p = 1; p < size; p++) {

           val = list.get(p);

           q = p - 1;

           while (q >= 0 && list.get(q) > val) {

               list.set(q + 1, list.get(q));

               q = q - 1;

           }

           list.set(q + 1, val);

       }

   }

   static void mergeSort(ArrayList<Integer> list, int low, int high) {

       if (low < high && (high - low) >= 1) {

           int mid = (high + low) / 2;

           mergeSort(list, low, mid);

           mergeSort(list, mid + 1, high);

           merger(list, low, mid, high);

       }

   }

   static void merger(ArrayList<Integer> list, int low, int mid, int high) {

       ArrayList<Integer> mergedArray = new ArrayList<Integer>();

       int left = low;

       int right = mid + 1;

       while (left <= mid && right <= high) {

           if (list.get(left) <= list.get(right)) {

               mergedArray.add(list.get(left));

               left++;

           } else {

               mergedArray.add(list.get(right));

               right++;

           }

       }

       while (left <= mid) {

           mergedArray.add(list.get(left));

           left++;

       }

       while (right <= high) {

           mergedArray.add(list.get(right));

           right++;

       }

       int i = 0;

       int j = low;

       while (i < mergedArray.size()) {

           list.set(j, mergedArray.get(i++));

           j++;

       }

   }

   public static void main(String[] args) throws Exception {

       ArrayList<Integer> list = new ArrayList<>();

       Random rand = new Random(System.currentTimeMillis());

       for (int i = 0; i < 10000; i++) {

           list.add(rand.nextInt(256));

       }

       long start = System.currentTimeMillis();

       selectionSort(list);

       int sel = (int) (System.currentTimeMillis() - start);

       System.out.println("Selection Sort time (in ms): " + sel);

       list.clear();

       //

       rand = new Random(System.currentTimeMillis());

       for (int i = 0; i < 10000; i++) {

           list.add(rand.nextInt(256));

       }

       start = System.currentTimeMillis();

       insertionSort(list);

       int ins = (int) (System.currentTimeMillis() - start);

       System.out.println("Insertion Sort time (in ms): " + ins);

       list.clear();

       //

       rand = new Random(System.currentTimeMillis());

       for (int i = 0; i < 10000; i++) {

           list.add(rand.nextInt(256));

       }

       start = System.currentTimeMillis();

       bubbleSort(list);

       int bub = (int) (System.currentTimeMillis() - start);

       System.out.println("Bubble Sort time (in ms): " + bub);

       list.clear();

       //

       rand = new Random(System.currentTimeMillis());

       for (int i = 0; i < 10000; i++) {

           list.add(rand.nextInt(256));

       }

       start = System.currentTimeMillis();

       mergeSort(list, 0, list.size() - 1);

       int mer = (int) (System.currentTimeMillis() - start);

       System.out.println("Merge Sort time (in ms): " + mer);

       long m = Math.min(Math.min(sel, ins), Math.min(bub, mer));

       if (m == sel)

           System.out.println("Selection Sort is fastest");

       else if (m == ins)

           System.out.println("insertion Sort is fastest");

       else if (mer == m)

           System.out.println("Merge Sort is fastest");

       else if (m == bub)

           System.out.println("Bubble Sort is fastest");

   }

}