I have Implemented the algorithms for insertion sort, Merge Sort and Quicksort. I want to use find a timing system in JAVA like $$timing$$ in C$++$ to compare the run time of the algorithms on inputs consisting of only positive integers.

Please be able to input any size such as input sizes of $1000,10,000,50,000,100000,150000,200,000,250,000,300,000.$

The input can be generated randomly using the rand$()$ function in C$++$ but I don$$t know how in java. Please use a vector structure like in C$++$ STL to store the integers.

Also I would like to be able to test the algorithms by using a small input $($size $20)$ and print the list to make sure the algorithm sorts the list properly.

Here is the code for the algorithms:

import java.util.Arrays;

public class SortingAlgorithms

$\{$

public static void main$($String$[]$ args$)$

$\{$

int$[]$ numbers $=\{10,9,8,7,1,2,3,6,5,4\}$;

System.out.println$("$ UNSORTED: $"+$ Arrays.toString$($numbers$))$;

insertionSort$($numbers$)$;

System.out.println$("$Insertion sort SORTED: $"+$ Arrays.toString$($numbers$))$;

mergeSort$($numbers$,0,$ numbers.length $-1)$;

System.out.println$("$ Merge sort SORTED: $"+$ Arrays.toString$($numbers$))$;

quicksort$($numbers$,0,$ numbers.length $-1)$;

System.out.println$("$ Quick sort SORTED: $"+$ Arrays.toString$($numbers$))$;

$\}$

private static void insertionSort$($int$[]$ numbers$)\{$

for $($int i $=1$; i $<$ numbers.length; i$++)\{$

int j $=$ i;

while $($j $>0$ && numbers$[$j$]<$ numbers$[$j $-1])\{$

int temp $=$ numbers$[$j$]$;

numbers$[$j$]=$ numbers$[$j $-1]$;

numbers$[$j $-1]=$ temp;

j$--$;

$\}$

$\}$

$\}$

private static void merge$($int$[]$ numbers, int i$,$ int j$,$ int k$)\{$

int mergedSize $=$ k $-$ i $+1$;

int$[]$ mergedNumbers $=$ new int$[$mergedSize$]$;

int mergePos $=0$;

int leftPos $=$ i;

int rightPos $=$ j $+1$;

while $($leftPos $<=$ j && rightPos $<=$ k$)\{$

if $($numbers$[$leftPos$]<=$ numbers$[$rightPos$])\{$

mergedNumbers$[$mergePos$]=$ numbers$[$leftPos$]$;

leftPos$++$;

$\}$

else $\{$

mergedNumbers$[$mergePos$]=$ numbers$[$rightPos$]$;

rightPos$++$;

$\}$

mergePos$++$;

$\}$

while $($leftPos $<=$ j$)\{$

mergedNumbers$[$mergePos$]=$ numbers$[$leftPos$]$;

leftPos$++$;

mergePos$++$;

$\}$

while $($rightPos $<=$ k$)\{$

mergedNumbers$[$mergePos$]=$ numbers$[$rightPos$]$;

rightPos$++$;

mergePos$++$;

$\}$

for $($mergePos $=0$; mergePos $<$ mergedSize; mergePos$++)\{$

numbers$[$i $+$ mergePos$]=$ mergedNumbers$[$mergePos$]$;

$\}$

$\}$

private static void mergeSort$($int$[]$ numbers, int i$,$ int k$)\{$

int j $=0$;

if $($i $<$ k$)\{$

j $=($i $+$ k$)/2$;

mergeSort$($numbers$,$ i$,$ j$)$;

mergeSort$($numbers$,$ j $+1,$ k$)$;

merge$($numbers$,$ i$,$ j$,$ k$)$;

$\}$

$\}$

private static int partition$($int$[]$ numbers, int startIndex, int endIndex$)\{$

int midpoint $=$ startIndex $+($endIndex $-$ startIndex$)/2$;

int pivot $=$ numbers$[$midpoint$]$;

int low $=$ startIndex;

int high $=$ endIndex;

boolean done $=$ false;

while $(!$done$)\{$

while $($numbers$[$low$]<$ pivot$)\{$

low $=$ low $+1$;

$\}$

while $($pivot $<$ numbers$[$high$])\{$

high $=$ high $-1$;

$\}$

if $($low $>=$ high$)\{$

done $=$ true;

$\}$

else $\{$

int temp $=$ numbers$[$low$]$;

numbers$[$low$]=$ numbers$[$high$]$;

numbers$[$high$]=$ temp;

low$++$;

high$--$;

$\}$

$\}$

return high;

$\}$

private static void quicksort$($int$[]$ numbers, int startIndex, int endIndex$)\{$

$//$ Only attempt to sort the array segment if there are

$//$ at least $2$ elements

if $($endIndex $<=$ startIndex$)\{$

return;

$\}$

$//$ Partition the array segment

int high $=$ partition$($numbers$,$ startIndex, endIndex$)$;

$//$ Recursively sort the left segment

quicksort$($numbers$,$ startIndex, high$)$;

$//$ Recursively sort the right segment

quicksort$($numbers$,$ high $+1,$ endIndex$)$;

$\}$

$\}$