import java.util.ArrayList;

public class Sort {
    public static ArrayList <String> songTitles = new ArrayList<String>();
    public Sort(ArrayList <String> songTitles) {
        this.songTitles = songTitles;
    }
    public static int getLength(String title) {
        return title.length();
    }
}

// Bubble sort
public class BubbleSort extends Sort {
    public BubbleSort(ArrayList <String> songTitles) {
        super(songTitles);
    }
    public static void DoBubbleSort(String title) {
        songTitles.add(title);
        int arrayListLength = songTitles.size();
        if (arrayListLength==0) {
            System.out.println("yeah");
        } else {
            String temp = "";
            for (int i = 0; i<arrayListLength; i++) {
                for (int j=1; j<(arrayListLength-i); j++) {
                    if (getLength(songTitles.get(j-1))>getLength(songTitles.get(j))) {
                        temp = songTitles.get(j-1);
                        songTitles.set(j-1, songTitles.get(j));
                        songTitles.set(j, temp);
                    }
                }
            }
        }
    }
}

public class InsertionSort extends Sort {
    public InsertionSort(ArrayList <String> songTitles) {
        super(songTitles);
    }

    public static void DoInsertionSort(String title) {
        songTitles.add(title);
        int arrayListLength = songTitles.size();
        if (arrayListLength==0) {
            System.out.println("yeah");
        } else {
            for (int i = 0; i<arrayListLength; i++) {
                String temp = songTitles.get(i);
                int j = i-1;
                while (j >= 0 && getLength(songTitles.get(j)) > getLength(temp)) {
                    songTitles.set(j+1, songTitles.get(j));
                    j=j-1;
                }
                songTitles.set(j+1, temp);
            }
        }
    }
}

public class SelectionSort extends Sort {
    public SelectionSort(ArrayList <String> songTitles) {
        super(songTitles);
    }

    public static void DoSelectionSort(String title) {
        songTitles.add(title);
        int arrayListLength = songTitles.size();
        if (arrayListLength==0) {
            System.out.println("yeah");
        } else {
            for (int i = 0; i<arrayListLength-1; i++) {
                int min_idx = i;
                for (int j = i+1; j<arrayListLength; j++) {
                    if (getLength(songTitles.get(j))<getLength(songTitles.get(min_idx))) {
                        min_idx = j;
                    }
                }
                String temp = songTitles.get(min_idx);
                songTitles.set(min_idx, songTitles.get(i));
                songTitles.set(i, temp);
            }
        }
    }
}

public class MergeSort extends Sort {
    public MergeSort(ArrayList <String> songTitles) {
        super(songTitles);
    }

    public static void DoMergeSort(String title, int m, int l, int r) {
        songTitles.add(title);
        int arrayListLength = songTitles.size();
        if (arrayListLength==0) {
            System.out.println("yeah");
        } else {
            int n1 = m - l + 1; 
            int n2 = r - m; 
            int L[] = new int[n1]; 
            int R[] = new int[n2];
            for (int i = 0; i < n1; ++i) 
            L[i] = arr[l + i]; 
            for (int j = 0; j < n2; ++j) 
            R[j] = arr[m + 1 + j]; 
            int i = 0, j = 0; 
            
            for (int i = 0; i<arrayListLength-1; i++) {
                int min_idx = i;
                for (int j = i+1; j<arrayListLength; j++) {
                    if (getLength(songTitles.get(j))<getLength(songTitles.get(min_idx))) {
                        min_idx = j;
                    }
                }
                String temp = songTitles.get(min_idx);
                songTitles.set(min_idx, songTitles.get(i));
                songTitles.set(i, temp);
            }
        }
    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList <String> songTitles = new ArrayList<String>();
        songTitles.add("blue");
        songTitles.add("fuschia");
        songTitles.add("pink");
        songTitles.add("red");
        songTitles.add("yellow");
        songTitles.add("purple");
        SelectionSort select = new SelectionSort(songTitles);
        select.DoSelectionSort("green");
        System.out.println(songTitles);
    }
}
Test.main(null);