“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”

In a few words

Understand the basic algorithm series of sorting algorithm – merge sort

Key point: Time complexity O(n*logn).

An algorithm problem

Let’s start with a case study.

Two ordered arrays, output an ascending array

Ary1 = {4, 6, 7}, ary2 = {1, 3, 10, 19}

By taking out the values of the arrays for comparison, since there are already two ordered arrays, each array is either in ascending or descending order. When taking out the values of the arrays for comparison, the smallest one is put into the new array. NewAry =[]

Ary1 [0] > ary2[0]; newAry = [1]; newAry = [1]; newAry = [1];

Ary1 [0] > ary2[1]; newAry = [1, 3];

Ary1 [0] < ary2[2]; newAry = [1, 3, 4];

NewAry = [1, 3, 4, 6]; newAry = [1, 3, 4, 6];

NewAry = [1, 3, 4, 6,7]; newAry = [1, 3, 4, 6,7];

NewAry =[1,3,4,6,7,10,19] newAry=[1,3,4,6,7,10,19]

JavaScript implements the above process

Function sortGuibing(ary1, ary2) {let newAry = [] let I = 0, j = 0; do { if (ary1[i] >= ary2[j]) { newAry.push(ary2[j]); j++; } else { newAry.push(ary1[i]); i++; } if (i == ary1.length && j < ary2.length) newAry = newAry.concat(ary2.slice(j, ary2.length)) if (j == ary2.length && i < ary1.length) newAry = newAry.concat(ary1.slice(i, ary1.length)) } while (i < ary1.length && j < ary2.length) console.log(newAry) }Copy the code

Golang implements this process

Func sortGuibing(ary1, ary2 []int) {newAry := make([]int, 0) i := 0 j := 0 for i < len(ary1) && j < len(ary2) { if ary1[i] > ary2[j] { newAry = append(newAry, ary2[j]) j++ } else { newAry = append(newAry, ary1[i]) i++ } if i == len(ary1) && j < len(ary2) { newAry = append(newAry, ary2[j:len(ary2)-1]...) } if j == len(ary2) && i < len(ary1) { newAry = append(newAry, ary1[i:len(ary1)-1]...) } } for _, v := range newAry { fmt.Print(v, ",") } }Copy the code

Merge sort

Merge sort, which merges ordered subsequences to get fully ordered sequences; That is, each subsequence is ordered first, and then the subsequence segments are ordered

So the premise of merge sort is that you need a subsequence that’s already sorted.

Adopt: divide and conquer.

Algorithm ideas

Sort an array

Split the array into two arrays, sort the two arrays, and merge them into a new array. If the split array is out of order, you can split and merge the two arrays separately. And so you recurse until you merge into an ordered array.

Golang implementation

Func sortGuibing(ary []int) {sortGuibing_sortAry(ary, 0, len(ary)-1) for _, V := range ary {FMT.Print(v, ",")}} /** ** flu. (ary []int, flu. int, Rary int) {if lary == rary {// only one element, } else {mid := (lary + rary) / 2 sortGuibing_sortAry(ary, lary, Sortguibing_sorgeary (ary, lary, mid+1, rary) rary) } } func sortGuibing_mergeAry(ary []int, lary, mid, rary int) { ldata := ary[lary:mid] rdata := ary[mid+1 : rary] i := 0 j := 0 k := lary for i < len(ldata) && j < len(rdata) { if ldata[i] > rdata[j] { ary[k] = rdata[j] j++ k++ } else {ary[k] = ldata[I] I ++ k++}} if I == len(ldata) &&j < len(rdata) { For _, v := range rdata[j:] {ary[k] = v k++}} if j == len(ldata) && I < len(rdata) {for _, v := range rdata[j:] {ary[k] = v k++}} For _, v := range ldata[I :] {ary[k] = v k++}}Copy the code

JavaScript implementation

function sortGuibing(ary) { sortGuibing_sort(ary, 0, ary.length - 1) console.log(ary) } function sortGuibing_sort(ary, llen, rlen) { if (llen == rlen) return; let mid = Math.floor((llen + rlen) / 2 ,0); sortGuibing_sort(ary, llen, mid); sortGuibing_sort(ary, mid + 1, rlen); sortGuibing_merge(ary, llen, mid+1, rlen); } function sortGuibing_merge(ary, llen, mid, rlen) { let ldata = ary.slice(llen, mid); let rdata = ary.slice(mid + 1, rlen); let i = 0, j = 0; let k = llen; while (i < ldata.length && j < rdata.length) { if (ldata[i] >= rdata[j]) { ary[k] = rdata[j] j++; k++; } else { ary[k] = ldata[i] i++; k++; } if (i == ldata.length && j < rdata.length) { rdata.forEach((v, m) => { if (m >= j) { ary[k] = v; k++; }}); } if (j == rdata.length && i < ldata.length) { ldata.forEach((v, m) => { if (m >= j) { ary[k] = v; k++; }}); }}}Copy the code