Create a Program to Solve Merge Sort Problems in Java Assignment Solution

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:

1. Divide the list in halves
2. Merge sort the first half
3. Merge sort the second half
4. 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 } } }