Merge is to merge two (or more than two) ordered tables into a new ordered table, that is, divide the sequence to be sorted into several subsequences, each subsequence is ordered. Then the ordered subsequences are combined into the overall ordered sequence.
Merge sorting is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. Merge the ordered subsequences to obtain a completely ordered sequence; that is, make each subsequence first order, and then make the subsequence segments order. If two ordered tables are merged into one ordered table, it is called 2-way merge.
The merge sorting algorithm is stable. The array requires additional space for O(n), and the linked list requires additional space for O(log(n)), and the time complexity is O(nlog(n)). The algorithm is not adaptive and does not require data. random reads.
How it works:
1. Apply for space so that its size is the sum of two sorted sequences, which is used to store the combined sequences
2. Set two pointers, the initial positions are the starting positions of the two sorted sequences respectively.
3. Compare the elements pointed to by two pointers, select relatively small elements and put them into the merge space, and move the pointer to the next position
4. Repeat step 3 until a pointer reaches the end of the sequence
5. Copy all the remaining elements of another sequence directly to the end of the merged sequence
Run the code
The code copy is as follows:
package com.zc.manythread;
import java.util.Random;
/**
* Ordering
* @author I'm
*
*/
public class MergeSort {
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void sort(int[] data, int left, int right) {
if (left >= right)
return;
// Find the intermediate index
int center = (left + right) / 2;
// Recursive the left array
sort(data, left, center);
// Recursive the right array
sort(data, center + 1, right);
// Merge
merge(data, left, center, right);
print(data);
}
/**
* Merge the two arrays, merge the first two arrays into order, and still order after merging
*
* @param data
* Array object
* @param left
* Index of the first element of the left array
* @param center
* The index of the last element of the left array, center+1 is the index of the first element of the right array
* @param right
* Index of the last element of the right array
*/
public static void merge(int[] data, int left, int center, int right) {
// Temporary array
int[] tmpArr = new int[data.length];
// Index of the first element of the right array
int mid = center + 1;
// third record the index of the temporary array
int third = left;
// cache the index of the first element of the left array
int tmp = left;
while (left <= center && mid <= right) {
// Take out the smallest from the two arrays and put it into the temporary array
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// Put the remaining parts into the temporary array in turn (in fact, only one of the two while will be executed)
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// Copy the contents of the temporary array back to the original array
// (The content of the original left-right range is copied back to the original array)
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "/t");
}
System.out.println();
}
/**
* Generate a random array
* @param count
* @return
*/
private static int[] createDate(int count) {
int[] data=new int[count];
Random rand = new Random();
boolean[] bool = new boolean[100];
int num = 0;
for (int i = 0; i < count; i++) {
do {
// If the generated number is the same, continue to loop
num = rand.nextInt(100);
} while (bool[num]);
bool[num] = true;
data[i]=num;
}
return data;
}
public static void main(String[] args) {
int[] data = createDate(10);
print(data);
mergeSort(data);
System.out.println("Sorted array:");
print(data);
}
}
Running results:
The above is all about this article, I hope you can like it.