NOTE

3.12 Merge Sort

Merge sort, its characteristics, process, and implementation.

Data Structures & AlgorithmsCreated 02/29/2020Updated 02/26/20241 min readhistorical

This is a historical learning note and may contain outdated or incomplete understanding.

1. Merge Sort

It uses the divide-and-conquer idea: divide a large problem into smaller problems and solve them recursively. Keep splitting the array in half until it is sorted (only one node remains), and finally merge the parts.

If the key to quick sort is partitioning, the key to merge sort is merging.

2. Characteristics

Stability: stable
In-place sorting: no
Complexity
- Time: O(nlogn)
  - For the standard merge-sort implementation here, even if the array is already sorted, the complexity is O(NlogN)
- Space: O(n)
Compared with insertion sort, insertion sort is faster for small-scale data

3. Process

4. Implementation


//O(NlogN)
func MergeSort(data []model.Comparable) {
	mergeSort(data, 0, len(data)-1)
}

func merge2(data []model.Comparable, left int, mid int, right int) {
	length := right - left + 1
	tmp := make([]model.Comparable, length)
	i := left
	j := mid + 1
	k := 0
	for i <= mid && j <= right {
		if data[i].CompareTo(data[j]) > 0 {
			tmp[k] = data[j]
			k++
			j++
		} else {
			tmp[k] = data[i]
			k++
			i++
		}
	}

	for i <= mid {
		tmp[k] = data[i]
		k++
		i++
	}
	for j <= right {
		tmp[k] = data[j]
		k++
		j++
	}

	k = 0
	i = left
	for i <= right {
		data[i] = tmp[k]
		i++
		k++
	}
}

func mergeSort(data []model.Comparable, left int, right int) {
	if left >= right {
		return
	}

	mid := (left + right) / 2
	mergeSort(data, left, mid)
	mergeSort(data, mid+1, right)

	merge(data, left, mid, right)
    // Or use the classic version
    //merge2(data, left, mid, right)
}

func merge(data []model.Comparable, left int, mid int, right int) {
	length := right - left + 1
	tmp := make([]model.Comparable, length)
	for i := 0; i < length; i++ {
		tmp[i] = data[i+left]
	}

	i := left
	j := mid + 1
	for k := left; k <= right; k++ {
		// The left array is exhausted
		if i > mid {
			data[k] = tmp[j-left]
			j++
		// The right array is exhausted
		} else if j > right {
			data[k] = tmp[i-left]
			i++
		// Element in the left array <= element in the right array
		} else if tmp[i-left].CompareTo(tmp[j-left]) <= 0 {
			data[k] = tmp[i-left]
			i++
		// Element in the left array > element in the right array
		} else {
			data[k] = tmp[j-left]
			j++
		}
	}
}

4.1. Test

func TestMergeSort(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	MergeSort(data)
	fmt.Println(data)
}

5. References

Discussion

JavaScript is required to load comments.Open the discussion on GitHub