// We want to keep the subarray arr[0..i-1] sorted

// So we start from the first element and go to the last element

// We will take the i-th element and insert it into the

// sorted subarray arr[0..i-1]

// We will do this by shifting all the elements in the

// sorted subarray arr[0..i-1] that are greater than

// arr[i] to the right by one position

// We will then insert arr[i] at the correct position

// in the sorted subarray arr[0..i-1]

import java.util.ArrayList;

public class BubbleSort {

public static ArrayList<Integer> bubble_sort(ArrayList<Integer> blist){

for (int i = 1; i < blist.size(); i++) {

int temp = blist.get(i);

int red = i - 1;

while (red >= 0 && blist.get(red) > temp) {

blist.set(red + 1, blist.get(red));

red--;

}

blist.set(red + 1, temp);

}

return blist;

}

// public static ArrayList<Integer> merge_sort(ArrayList<Integer> msort){

// }

}