Instructions
Objective
Write a java assignment to solve merge sort problems.
Requirements and Specifications
Merge sort is a sorting technique that sequences data by continuously merging items in a single sorted list. Every item in the original unordered list is merged with another, creating groups of two. Every two-item group is merged, creating groups of four and so on until there is one ordered list, as shown below.
The merge sort is basically as follows:
- Divide the list in halves
- Merge sort the first half
- Merge sort the second half
- Merge both halves back together
This merge sort lends itself well to recursion. The merge sort divides the array to be sorted into halves, sort these two sub-arrays separately, and then combine these sorted sub-arrays to produce solution to the original problem. Once the array is divided, the left sub-array is further divided into sub-arrays until the last sub-array has at most two values. At this point these two values are sorted; likewise, the sub-array to the neighbor (if any) this sorted array, is now sorted and is merged to the already sorted sub-list. Once the left sub-array is sorted and merged, the right sub-array is divided and sorted like the left. When both sub-arrays sorted, they are then merged.
merge_sort( int arr[], int left_index, int right_index)
{
if (right_index > left_index)
{
int mid = (left_index + right_index)/2;
int left_sublist[ ] = merge_sort( arr, left_index, mid);
int right_sublist[ ] = merge_sort( arr, mid+ 1, right_index,);
merge(arr, left_sublist, right_sublist);
}
}
Write a java assignment that implements the merge-sort merge sort
Source Code
public class App {
public static void main(String[] args) throws Exception {
// Define array
int arr[] = {12, 11, 13, 5, 6, 7};
print_array(arr);
// Sort
merge_sort(arr, 0, arr.length-1);
print_array(arr);
}
static void print_array(int arr[]) {
/*
Helper function that Prints the array
*/
System.out.print("[");
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if(i < arr.length-1) {
System.out.print(", ");
}
}
System.out.print("]\n");
}
static void merge(int arr[], int left, int mid, int right)
{
/*
Given an array, this function
slices that array in two parts: left and right
It then merges the two arrays while sorting them
*/
// First, get the sizes of the arrays
int n1 = (mid-left)+1;
int n2 = right-mid;
/*
Create two arrays to hold the left and right values
*/
int left_sublist[] = new int[n1];
int right_sublist[] = new int[n2];
// Fill them
for(int i = 0; i < n1; i++) {
left_sublist[i] = arr[left+i];
}
for(int i = 0; i < n2; i++) {
right_sublist[i] = arr[mid+1+i];
}
int i = 0, j = 0;
int k = left;
while(i < n1 && j < n2) {
if(left_sublist[i] <= right_sublist[j]) { // left element is smaller than the right element, so put it into arr
arr[k] = left_sublist[i];
i++;
}
else{
arr[k] = right_sublist[j]; // right element is smaller than left element, so put the right element before left element
j++;
}
k++;
}
// Check if there are sill elements in the left part that has to be added to the main array
while(i < n1) {
arr[k] = left_sublist[i];
i++;
k++;
}
// Check if there are still elements in the right part that has to be added to the main array
while(j < n2) {
arr[k] = right_sublist[j];
j++;
k++;
}
}
static void merge_sort(int arr[], int left_index, int right_index)
{
// Check that left index is smaller than right index in order to avoid IndexOutOfBoundsException
if(left_index < right_index) {
int mid = (left_index + right_index)/2; // mid index
// sort both halves
merge_sort(arr, left_index, mid); // sort left part
merge_sort(arr, mid+1, right_index); // sort right part
// merge
merge(arr, left_index, mid, right_index); // merge
}
}
}