This post was originally posted on my blog

preface

This series includes ten classic sorting algorithms.

  • The language used is Java
  • The structure is: define abstract classesSortIt implements swap, size comparison and so on. For example, if you swap two values, just pass in the subscript. All other concretely sorted classes inherit from abstract classesSort. So we can focus on the algorithm itself.
/* * Return value is 0, indicating array[i1] == array[i2] * return value is less than 0, indicating array[i1] < array[i2] * return value is greater than 0, indicating array[i1] < array[i2] * return value is greater than 0. Array [i1] > array[i2] */ protected int CMP (int i1, int i2) {return array[i1].compareTo(array[i2]);
	}
	
	protected int cmp(T v1, T v2) {
		return v1.compareTo(v2);
	}
	
	protected void swap(int i1, int i2) {
		T tmp = array[i1];
		array[i1] = array[i2];
		array[i2] = tmp;
	}

Copy the code

What is merge sort

  • Mergesort is an efficient sorting algorithm created on merge operations with an efficiency of O(nlog n). It was first proposed in 1945 by John von Neumann. This algorithm is a very typical application of Divide and Conquer, and each level of divide-and-conquer recursion can be performed simultaneously.

An overview of the

  • Divide and conquer:

    • Split: To recursively divide the current sequence into equal halves.
    • Integration: The integration of subsequences from the previous step while preserving the order of the elements (merge).

Merge operation

  • Merge, also known as merge algorithm, refers to the operation of merging two already sorted sequences into a single sequence. Merge sort algorithms rely on merge operations.

Recursion (top-down)

  • Apply for a space that is the sum of two sorted sequences and is used to store the combined sequence
  • Sets two Pointers, starting at the start of two sorted sequences
  • Compare the elements to which the two Pointers point, place the smaller element into the merge space, and move the pointer to the next position
  • Repeat step 3 until a pointer reaches the end of the sequence
  • Copies all remaining elements of the other sequence directly to the end of the merged sequence

Bottom-up iterative method

The principle is as follows (assuming a sequence of n elements) :

  • Merge each two adjacent digits of the sequence to form CEIL (N /2) sequences, and each sequence contains two/one element after sorting
  • If the number of sequences at this time is not one, the above sequences are merged again to form CEIL (N /4) sequences, and each sequence contains four/three elements
  • Repeat step 2 until all elements are sorted, that is, the sequence number is 1

Space-time complexity

  • Best time complexity: O(nlogn)
  • Worst, average time complexity: O(nlogn)
  • Space complexity: O(n)

Algorithm stability

  • Merge sort is a stable sorting algorithm.

Is it in place

  • What is the in situ algorithm?
    • Not dependent on additional resources or on a few additional resources, relying only on the output to override the input
    • The spatial complexity of 𝑂(1) can be considered as in situ algorithm
  • The non-in-situ algorithm is called not-in-place or out-of-place
  • Merge sort is not in-place

code

package YZ.Sort;

public class MergeSort <T extends Comparable<T>> extends Sort<T> {

	private T[] leftArray;
	@Override
	protected void sort() {
		// TODO Auto-generated method stub
		leftArray = (T[]) new Comparable[array.length>>1];
		sort(0, array.length);
	}

	/**
	 * 对 [begin, end) 范围的数据进行归并排序
	 */
	private void sort(int begin,int end) {
		if (end-begin<2) {
			return; } int mid = (begin + end)>>1; sort(begin, mid); sort(mid,end); merge(begin, mid, end); Private void merge(int begin, int mid, int end) {int li = 0, private void merge(int begin, int mid, int end); Le = mid;// leftArray (based on leftArray) int ri = mid,re=end;// right array (based on array) int ai = begin; //array index // back up leftArrayfor(int i = li; i < le; I ++) {// copy the leftArray to leftArray leftArray[I] = array[begin+ I]; }while(li<le) {// The left side does not endif(ri<re && cmp(array[ri], leftArray[li])<0) { array[ai++] = array[ri++]; // Copy the right array to array}else{ array[ai++] = leftArray[li++]; // Copy the left array to array}}// Note that if CMP is changed to <=, it will lose stability}}Copy the code

The results of

Data source: Randomly generate 10000 data from 1 to 20000 to test

Integer[] array = Integers.random(10000, 1, 20000);

The results are as follows:

[BubbleSort] Stability: True Time: 0.481s(481ms

[BubbleSort1] Stability: true Time: 0.428s(428ms

[BubbleSort2] Stability: true Time: 0.405s(405ms

[InsertionSort1] Stability: true Time: 0.239s(239ms) Comparison times: 24684,200 exchange times: 24674,200

[InsertionSort2] Stability: true Time: 0.186s(186ms) Comparison times: 24684,200 exchange times: 0

[InsertionSort3] Stability: true Time-consuming: 0.114s(114ms) Comparison times: 119,900 exchange times: 0

[HeapSort] Stability: false Time: 0.005s(5ms) Comparison count: 235,300 exchange count: 9999

[MergeSort] Stability: true Time: 0.004s(4ms) Comparison times: 120,500 exchange times: 0

You can see that merge sort performance is still quite high.

Code Address:

  • The code in git is at github