Tóm Tắt
Merge Sort Java With Code Examples
Merge Sort Java With Code Examples
In this session, we will try our hand at solving the Merge Sort Java puzzle by using the computer language. The following piece of code will demonstrate this point.
package Arrays;
import java.util.Arrays;
public class MergeSort {
static void sort(int[] arr) {
if (arr.length < 2) return;
int mid = arr.length / 2;
int[] left_half = new int[mid];
int[] right_half = new int[arr.length - mid];
// copying the elements of array into left_half
for (int i = 0; i < mid; i++) {
left_half[i] = arr[i];
}
// copying the elements of array into right_half
for (int i = mid; i < arr.length; i++) {
right_half[i - mid] = arr[i];
}
sort(left_half);
sort(right_half);
merge(arr, left_half, right_half);
}
static void merge(int[] arr, int[] left_half, int[] right_half) {
int i = 0, j = 0, k = 0;
while (i < left_half.length && j < right_half.length) {
if (left_half[i] < right_half[j]) {
arr[k++] = left_half[i++];
}
else {
arr[k++] = right_half[j++];
}
}
while (i < left_half.length) {
arr[k++] = left_half[i++];
}
while (j < right_half.length) {
arr[k++] = right_half[j++];
}
}
public static void main(String[] args) {
int[] arr = {5, 1, 7, 3, 8, 0, 1, 5, 7, 2, 8, 9, -7, 4, -9, -3, 4};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
There are a variety of approaches that can be taken to solve the same problem Merge Sort Java. The remaining solutions are discussed further down.
public class MergeSort
{
public static void main(String[] args)
{
int i;
int values[] = new int[11];
for(i=0; i<values.length; i++) { values[i]=values.length-i; }
print(values);
sort(values,0,values.length-1);
print(values);
}
public static void sort(int[] numbers, int p,int r)
{
int q;
if(p<r)
{
q = (p+r)/2;
sort(numbers,p,q);
sort(numbers,q+1,r);
merge(numbers,p,q,r);
}
}
/**
* p, mid, and r are indices into the array such that p <= mid < r.
* The procedure assumes that the subarrays 'numbers[p..mid]' and 'numbers[mid+1..r]' are
* in sorted order. It merge them to form a single sorted subarray that replaces
* the current subarray 'numbers[p..r]'.
*/
private static void merge(int[] values, int p, int mid, int r)
{
int i,j,k;
int n1 = mid - p + 1;
int n2 = r - mid;
int[] left = new int[n1+1];
int[] right = new int[n2+1];
for(i=0; i<n1; i++)
{
left[i] = values[ p + i ];
}
for(j=0; j<n2; j++)
{
right[j] = values[mid + j + 1];
}
left[n1] = Integer.MAX_VALUE;
right[n2] = Integer.MAX_VALUE;
i=0; j=0;
for(k=p; k<=r; k++)
{
if(left[i]<=right[j])
{
values[k] = left[i];
i = i + 1;
}
else
{
values[k] = right[j];
j = j + 1;
}
}
}
public static void print(int[] numbers)
{
int i;
for(i=0; i<numbers.length; i++)
{
System.out.print(numbers[i]+ " ");
}
System.out.println();
}
}
# Merge Sorting is simple code:
# Python program for implementation of MergeSort
def merge(left,right):
merged_list = []
L,R = len(left),len(right)
i,j = 0,0
# Now checking left and right sorting and Copy data to temp arrays L[] and R[]
while i < L and j < R:
if left[i] < right[j]:
merged_list.append(left[i])
i += 1
else:
merged_list.append(right[j])
j += 1
# Checking if any element was left
if i < L:
merged_list += left[i:] # merge_list Add elements to the list.
# Checking if any element was left
elif j < R:
merged_list += right[j:] # merge_list Add elements to the list.
return merged_list
# Now merge sorting:
def merge_sort(arr):
if len(arr) <= 1:
return arr
# Finding the mid of the array
mid = len(arr)//2
# Dividing the array left and right elements
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left,right)
# input list:
arr = [[4,7,2,3],[23,45,3],[4,55,6,7,5][3],[5,1],[1,4]]
for i in arr:
sorted_list = merge_sort(i)
print("Original List:",i)
print("Sorted List:",sorted_list)
print()
We have demonstrated, with a plethora of illustrative examples, how to tackle the Merge Sort Java problem.
What is a merge sort in Java?
Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves.09-Jun-2022
What is merge sort with example?
Merge sort
What are the 3 case complexity of merge sort?
The list of size N is divided into a max of Logn parts, and the merging of all sublists into a single list takes O(N) time, the worst-case run time of this algorithm is O(nLogn) Best Case Time Complexity: O(n*log n) Worst Case Time Complexity: O(n*log n) Average Time Complexity: O(n*log n) The time complexity of 03-Aug-2022
What does merge sort do?
Merge sort is one of the most efficient sorting algorithms. It is based on the divide-and-conquer strategy. Merge sort continuously cuts down a list into multiple sublists until each has only one item, then merges those sublists into a sorted list.27-Oct-2021
What is best case of merge sort?
What is two way merge sort?
Two-way merge is the process of merging two sorted arrays of size m and n into a single sorted array of size (m + n). Merge sort compares two arrays, each of size one, using a two-way merge. The sorted sequence is saved in a new two-dimensional array.11-Sept-2021
What are the steps in merge sort?
Implementation of the merge sort algorithm is a three-step procedure. Divide, conquer, and combine. The divide component of the divide-and-conquer approach is the first step.31-Mar-2022
How many times is merge sort called?
So we expect to call MergeSort log n times. Since each recursive step is one half the length of n . Since we know that merge sort is O(n log n) could stop here as MergeSort is called log n times, the merge must be called n times.
Why is merge sort faster?
Merge sort is very efficient for sorting linked lists since linked lists cannot be randomly accessed, and in merge sort, we don’t require random access, while in quicksort, we need to randomly access elements. Quicksort is very efficient for sorting small datasets.
What is the run time of merge sort?
O(nLogn)
