Java Source Code - Merge Sort
Examples
Ansi.java
public class Ansi {
// Reset
public static final String RESET = "\u001B[0m";
// Foreground colors
public static final String BLACK = "\u001B[30m";
public static final String RED = "\u001B[31m";
public static final String GREEN = "\u001B[32m";
public static final String YELLOW = "\u001B[33m";
public static final String BLUE = "\u001B[34m";
public static final String MAGENTA = "\u001B[35m";
public static final String CYAN = "\u001B[36m";
public static final String WHITE = "\u001B[37m";
// Background colors
public static final String BLACK_BACKGROUND = "\u001B[40m";
public static final String RED_BACKGROUND = "\u001B[41m";
public static final String GREEN_BACKGROUND = "\u001B[42m";
public static final String YELLOW_BACKGROUND = "\u001B[43m";
public static final String BLUE_BACKGROUND = "\u001B[44m";
public static final String MAGENTA_BACKGROUND = "\u001B[45m";
public static final String CYAN_BACKGROUND = "\u001B[46m";
public static final String WHITE_BACKGROUND = "\u001B[47m";
// Bright foreground colors
public static final String BRIGHT_BLACK = "\u001B[90m";
public static final String BRIGHT_RED = "\u001B[91m";
public static final String BRIGHT_GREEN = "\u001B[92m";
public static final String BRIGHT_YELLOW = "\u001B[93m";
public static final String BRIGHT_BLUE = "\u001B[94m";
public static final String BRIGHT_MAGENTA = "\u001B[95m";
public static final String BRIGHT_CYAN = "\u001B[96m";
public static final String BRIGHT_WHITE = "\u001B[97m";
// Bright background colors
public static final String BRIGHT_BLACK_BACKGROUND = "\u001B[100m";
public static final String BRIGHT_RED_BACKGROUND = "\u001B[101m";
public static final String BRIGHT_GREEN_BACKGROUND = "\u001B[102m";
public static final String BRIGHT_YELLOW_BACKGROUND = "\u001B[103m";
public static final String BRIGHT_BLUE_BACKGROUND = "\u001B[104m";
public static final String BRIGHT_MAGENTA_BACKGROUND = "\
u001B[105m";
public static final String BRIGHT_CYAN_BACKGROUND = "\u001B[106m";
public static final String BRIGHT_WHITE_BACKGROUND = "\u001B[107m";
}
public classAnsi // Reset public static final = "\
u001B[0m" // Foreground colors public static final = "\
u001B[30m" public static final = "\u001B[31m" public static
final = "\u001B[32m" public static final = "\u001B[33m" public
static final = "\u001B[34m" public static final = "\u001B[35m"
public static final = "\u001B[36m" public static final = "\
u001B[37m" // Background colors public static final = "\
u001B[40m" public static final = "\u001B[41m" public static
final = "\u001B[42m" public static final = "\u001B[43m" public
static final = "\u001B[44m" public static final = "\u001B[45m"
public static final = "\u001B[46m" public static final = "\
u001B[47m" // Bright foreground colors public static final = "\
u001B[90m" public static final = "\u001B[91m" public static
final = "\u001B[92m" public static final = "\u001B[93m" public
static final = "\u001B[94m" public static final = "\u001B[95m"
public static final = "\u001B[96m" public static final = "\
u001B[97m" // Bright background colors public static final = "\
u001B[100m" public static final = "\u001B[101m" public static
final = "\u001B[102m" public static final = "\u001B[103m"
public static final = "\u001B[104m" public static final = "\
u001B[105m" public static final = "\u001B[106m" public static
final = "\u001B[107m"
Example01.java
import java.util.Arrays;
public class Example01 {
public static void main(String[] args) {
new Example01();
}
// Fields used for displaying what is happening in the recursive
calls
public boolean display = true;
public int depth = 0;
public Example01() {
int[] array = {9, 3, 65, 37, 92, 77, 12, 63, 95, 6, 23, 62, 7,
13, 81, 45};
System.out.println("unsorted: " + Arrays.toString(array));
mergeSort(array);
System.out.println("sorted: " + Arrays.toString(array));
}
/***
* O(n) algorithm
* Merges two sorted lists of numbers, stored within the same array.
* The first list, A, goes from [start]..[mid-1],
* the second list, B, goes from [mid]..[end] in the array.
* Duplicate values ARE allowed in this very of the merge algorithm.
* Once completed, both lists will be sorted, and will occupy the
* same space in the array, i.e. [start]..[end] will be sorted.
* @param array The array of values being sorted.
* @param start The start index of the first list.
* @param mid The start index of the second list. The first list
goes from start..(mid-1)
* @param end The end index of the second list.
*/
public void merge(int[] array, int start, int mid, int end) {
// Create a temporary list to contain the sorted list
// of the two lists in the array
int[] c = new int[end - start + 1];
// Initialise the cursors in each of the lists
int posA = start; // note: not zero
int posB = mid; // note: not zero
int posC = 0;
// While there is something in BOTH of the lists
// note: does not go to the array length, because start, mid and
// end define the sizes of the arrays
while (posA <= mid - 1 && posB <= end) {
// note: there is no EQUALS case, which eliminated
duplicates
// in the original algorith
if (array[posA] <= array[posB]) {
c[posC] = array[posA];
posA++;
} else {
c[posC] = array[posB];
posB++;
}
posC++;
}
// Something left in A? Copy it all.
while (posA <= mid - 1) {
c[posC] = array[posA];
posC++;
posA++;
}
// Something left in B? Copy it all.
while (posB <= end) {
c[posC] = array[posB];
posC++;
posB++;
}
// Copy c into the original array, overwritting the original
// lists A and B
for (int i = 0; i < c.length; i++) {
array[start + i] = c[i];
}
}
/***
* O(n log n) algorithm - not O(n^2)
* Sort the contents of a section of an array.
* @param array The values being sorted.
* @param start The starting index of values to be sorted.
* @param end The ending index of values to be sorted.
*/
public void mergeSort(int[] array, int start, int end) {
// An array of size 0 or 1 is sorted, so do nothing. Otherwise
// the sub-array needs to be sorted.
if (end > start) {
// Calculate the splitting index
int mid = (start + end) / 2;
// Just some code to display/trace what is happening - omit
in
// actual working code
if (display) {
System.out.printf("%s>> " + Ansi.GREEN +
"mergeSort(array, %d, %d): %s\n" + Ansi.RESET, "\t".repeat(depth),
start, end,
Arrays.toString(Arrays.copyOfRange(array, start, end + 1)));
System.out.printf("%sunsorted 1st half [%d..%d]: %s\n",
"\t".repeat(depth + 1),
start, mid,
Arrays.toString(Arrays.copyOfRange(array, start, mid + 1)));
System.out.printf("%sunsorted 2nd half [%d..%d]: %s\n",
"\t".repeat(depth + 1),
mid + 1, end,
Arrays.toString(Arrays.copyOfRange(array, mid + 1, end + 1)));
depth++;
}
// Recursive call to sort 1st half
mergeSort(array, start, mid);
// Recursive call to sort 2nd half
mergeSort(array, mid + 1, end);
// Merge both halves together to sort whole
merge(array, start, mid + 1, end);
// Just some code to display/trace what is happening - omit
in
// actual working code
if (display) {
depth--;
System.out.printf("%s<< " + Ansi.BRIGHT_MAGENTA +
"mergeSort(array, %d, %d)\n" + Ansi.RESET, "\t".repeat(depth), start,
end);
System.out.printf("%ssorted 1st half [%d..%d]: %s\n", "\
t".repeat(depth + 1),
start, mid,
Arrays.toString(Arrays.copyOfRange(array, start, mid + 1)));
System.out.printf("%ssorted 2nd half [%d..%d]: %s\n", "\
t".repeat(depth + 1),
mid + 1, end,
Arrays.toString(Arrays.copyOfRange(array, mid + 1, end + 1)));
System.out.printf("%smerged [%d..%d]: %s\n", "\
t".repeat(depth + 1),
start, end,
Arrays.toString(Arrays.copyOfRange(array, start, end + 1)));
}
}
}
public void mergeSort(int[] array) {
mergeSort(array, 0, array.length - 1);
}
}
import java.util.Arrayspublic classExample01 public static void
main[] new // Fields used for displaying what is
happening in the recursive calls public boolean = true public int
= 0 public Example01 int[] = 9 3 65 37 92 77 12 63 95 6 23
62 7 13 81 45 outprintln"unsorted: " + toString
outprintln"sorted: " + toString /*** * O(n) algorithm *
Merges two sorted lists of numbers, stored within the same array. *
The first list, A, goes from [start]..[mid-1], * the second list, B,
goes from [mid]..[end] in the array. * Duplicate values ARE allowed
in this very of the merge algorithm. * Once completed, both lists
will be sorted, and will occupy the * same space in the array, i.e.
[start]..[end] will be sorted. * @param array The array of values
being sorted. * @param start The start index of the first list.
* @param mid The start index of the second list. The first list goes
from start..(mid-1) * @param end The end index of the second list.
*/ public void mergeint[] int int int // Create a
temporary list to contain the sorted list // of the two lists in
the array int[] = new int[ - + 1] // Initialise the
cursors in each of the lists int = // note: not zero int
= // note: not zero int = 0 // While there is something
in BOTH of the lists // note: does not go to the array length,
because start, mid and // end define the sizes of the arrays
while <= - 1 && <= // note: there is no EQUALS case,
which eliminated duplicates // in the original algorith
if [] <= [] [] = [] ++ else
[] = [] ++ ++ //
Something left in A? Copy it all. while <= - 1 [] =
[] ++ ++ // Something left in B?
Copy it all. while <= [] = [] ++
++ // Copy c into the original array, overwritting the
original // lists A and B for int = 0 < length ++
[ + ] = [] /*** * O(n log n) algorithm - not O(n^2)
* Sort the contents of a section of an array. * @param array The
values being sorted. * @param start The starting index of values to
be sorted. * @param end The ending index of values to be sorted.
*/ public void mergeSortint[] int int // An array of size
0 or 1 is sorted, so do nothing. Otherwise // the sub-array needs
to be sorted. if > // Calculate the splitting index
int = + / 2 // Just some code to display/trace what is
happening - omit in // actual working code if
outprintf"%s>> " + GREEN + "mergeSort(array, %d, %d): %s\n" + RESET "\
t"repeat toStringcopyOfRange + 1
outprintf"%sunsorted 1st half [%d..%d]: %s\n" "\t"repeat + 1
toStringcopyOfRange + 1 outprintf"%sunsorted 2nd half
[%d..%d]: %s\n" "\t"repeat + 1 + 1
toStringcopyOfRange + 1 + 1 +
+ // Recursive call to sort 1st half
// Recursive call to sort 2nd half + 1 // Merge
both halves together to sort whole + 1 // Just
some code to display/trace what is happening - omit in //
actual working code if --
outprintf"%s<< " + BRIGHT_MAGENTA + "mergeSort(array, %d, %d)\n" + RESET
"\t"repeat outprintf"%ssorted 1st half [%d..%d]: %s\n"
"\t"repeat + 1 toStringcopyOfRange + 1
outprintf"%ssorted 2nd half [%d..%d]: %s\n" "\t"repeat + 1
+ 1 toStringcopyOfRange + 1 + 1 outprintf"%smerged
[%d..%d]: %s\n" "\t"repeat + 1
toStringcopyOfRange + 1 public void
mergeSortint[] 0 length - 1
Example02.java
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Example02 {
public static void main(String[] args) {
new Example02();
}
public Example02() {
FoodItem[] menu = new FoodItem[100];
int menuCount = 0;
//region Load food data from text file
try (BufferedReader br = new BufferedReader(new
FileReader("Items.txt"))) {
String line;
while ((line = br.readLine()) != null) {
String[] parts = line.split(",");
FoodItem newOne = new FoodItem(parts[0], parts[1],
parts[2], Integer.parseInt(parts[3]), Double.parseDouble(parts[4]));
menu[menuCount] = newOne;
menuCount++;
}
} catch (IOException e) {
e.printStackTrace();
}
//endregion
//region Create code index
IndexItem[] codeIndex = new IndexItem[menuCount];
for (int i = 0; i < menuCount; i++) {
IndexItem temp = new IndexItem();
temp.key = menu[i].code;
temp.position = i;
codeIndex[i] = temp;
}
mergeSort(codeIndex, 0, menuCount - 1);
//endregion
//region Create description index
IndexItem[] descIndex = new IndexItem[menuCount];
for (int i = 0; i < menuCount; i++) {
IndexItem temp = new IndexItem();
temp.key = menu[i].description;
temp.position = i;
descIndex[i] = temp;
}
mergeSort(descIndex, 0, menuCount - 1);
//endregion
//region Allow user to query indices
System.out.println("Enter the code of item you would like to
display. Press enter to stop");
try (BufferedReader br = new BufferedReader(new
InputStreamReader(System.in))) {
String txt = br.readLine();
while (!txt.equals("")) {
IndexItem temp = binarySearchRecursive(codeIndex, txt,
0, menuCount - 1);
if (temp == null)
System.out.println("Item not found!");
else
System.out.println(menu[temp.position]);
System.out.println("Enter the code of item you would
like to display. Press enter to stop");
txt = br.readLine();
}
System.out.println("Enter the description of item you would
like to display. Press enter to stop");
txt = br.readLine();
while (!txt.equals("")) {
IndexItem temp = binarySearchRecursive(descIndex, txt,
0, menuCount - 1);
if (temp == null)
System.out.println("Item not found!");
else
System.out.println(menu[temp.position]);
System.out.println("Enter the description of item you
would like to display. Press enter to stop");
txt = br.readLine();
}
} catch (IOException e) {
e.printStackTrace();
}
//endregion
}
//region Sort methods
public void merge(IndexItem[] array, int start, int mid, int end) {
IndexItem[] c = new IndexItem[end - start + 1];
int posA = start;
int posB = mid;
int posC = 0;
while (posA <= mid - 1 && posB <= end) {
if (array[posA].key.compareTo(array[posB].key) <= 0) {
c[posC] = array[posA];
posA++;
} else {
c[posC] = array[posB];
posB++;
}
posC++;
}
while (posA <= mid - 1) {
c[posC] = array[posA];
posC++;
posA++;
}
while (posB <= end) {
c[posC] = array[posB];
posC++;
posB++;
}
System.arraycopy(c, 0, array, start, c.length);
}
public void mergeSort(IndexItem[] array, int start, int end) {
if (end > start) {
int mid = (start + end) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid + 1, end);
}
}
//endregion
//region Search method
public IndexItem binarySearchRecursive(IndexItem[] inputArray,
String key, int min, int max) {
if (min > max) {
return null;
} else {
int mid = (min + max) / 2;
if (key.equals(inputArray[mid].key)) {
return inputArray[mid];
} else if (key.compareTo(inputArray[mid].key) < 0) {
return binarySearchRecursive(inputArray, key, min, mid -
1);
} else {
return binarySearchRecursive(inputArray, key, mid + 1,
max);
}
}
}
//endregion
}
import java.io.BufferedReaderimport java.io.FileReaderimport
java.io.IOExceptionimport java.io.InputStreamReaderpublic classExample02
public static void main[] new public Example02
[] = new [100] int = 0 //region Load food data from text
file try = new new "Items.txt" while
= readLine != null [] = split"," = new
[0] [1] [2] parseInt[3] parseDouble[4] [] =
++ catch printStackTrace
//endregion //region Create code index [] = new []
for int = 0 < ++ = new key = []code
position = [] = 0 - 1 //endregion
//region Create description index [] = new [] for int =
0 < ++ = new key = []description
position = [] = 0 - 1 //endregion
//region Allow user to query indices outprintln"Enter the code of
item you would like to display. Press enter to stop" try = new
new in = readLine while !equals""
= 0 - 1 if == null outprintln"Item
not found!" else outprintln[position]
outprintln"Enter the code of item you would like to display. Press enter
to stop" = readLine
outprintln"Enter the description of item you would like to display.
Press enter to stop" = readLine while !equals""
= 0 - 1 if == null outprintln"Item
not found!" else outprintln[position]
outprintln"Enter the description of item you would like to display.
Press enter to stop" = readLine
catch printStackTrace
//endregion //region Sort methods public void merge[] int
int int [] = new [ - + 1] int = int =
int = 0 while <= - 1 && <= if
[]keycompareTo[]key <= 0 [] = [] ++
else [] = [] ++ ++
while <= - 1 [] = [] ++ ++
while <= [] = [] ++ ++
arraycopy 0 length public void mergeSort[] int int
if > int = + / 2 + 1
+ 1 //endregion //region Search method public
binarySearchRecursive[] int int if > return
null else int = + / 2 if equals[]key
return [] else if compareTo[]key < 0 return
- 1 else return + 1
//endregion
FoodItem.java
public class FoodItem {
public String code;
public String description;
public String category;
public double price;
public int stock;
public FoodItem(String code, String description, String category,
int stock, double price) {
this.code = code;
this.description = description;
this.category = category;
this.price = price;
this.stock = stock;
}
@Override
public String toString() {
return code + ", " + description + ", " + category + ", R" +
price + " Stock: " + stock;
}
}
public classFoodItem public public public public
double public int public FoodItem int double
thiscode = thisdescription = thiscategory =
thisprice = thisstock = @Override public toString
return + ", " + + ", " + + ", R" + + " Stock: " +
IndexItem.java
public class IndexItem {
public String key;
public int position;
}
public classIndexItem public public int
