📗Algorithm idea of divide and rule
🔑 Break down the problem into two or more smaller problems
🔑 Solve each small problem separately
🔑Combine the answers to each small question to get the solution to the original question
📚 Merge Sort
🐇Sorting Thoughts by Dividing and Solving
 Sorting algorithm using divide and conquer method:
 Arrange n elements in nonincreasing order
 If n is 1, the algorithm terminates;
 otherwise
 split this collection of elements into two or more subcollections
 Sort each subcollection separately
 Merge sorted subsets into one set
 That is, first make each subsequence in order, and then make the subsequences in order
🐇 Pseudocode of sorting algorithm
template<class T> void sort( T E, int n) {//Sort n elements in E, k is a global variable if(n >= k) { i = n/k; j = ni; make A Include E in the front i elements make B Include E the rest of j elements sort(A,i); sort(B,j); merge(A,B,E,i,j);//Merge A and B into E } else Use the insertion sort algorithm to E put in order }
🐇 Divide and rule the time of the sorting algorithm
Let t(n) be the worstcase time spent by the divideandmatch sorting algorithm
But k=2, t(n) is the smallest, t(n)=O(nlogn)
🔑 Merge Sort  Divide and Sorting Algorithm with k=2
🐇Merge sort flow chart
🐇 Merge sort implementation
🥕 Two groups of merging functions are realized
🍃Two groups are merged to realize the idea
 Merge two ordered segments
 c[startOfFirst:endOfFirst] and c[endOfFirst+1:endOfSecond]
 result segment d[startOfFirst:endOfSecond]
 first and second are respectively the cursors of the two segments to be merged, and result is the cursor to track the position of the next element in the merged result segment.
 Initial: first=startOfFirst, second = endOfFirst+1, result = startOfFirst;
 When the two merged segments have not been processed, loop:
 Compare the elements pointed by first and second, place the smaller one in the position pointed by result, and add 1 to the cursor and result for the smaller one
 Copy the elements in the unprocessed segment to d in turn.
🍃Two sets of merge implementation code
template<class T> void merge(T c[],T d[],int startOfFirst,int endOfFirst, int endOfSecond) { int first = startOfFirst,//Cursor for the first paragraph second = endOfFirst+1,//Cursor for the second paragraph result = startOfFirst;//result section cursor //When the two merged segments have not been processed, the merge will continue while((first <= endOfFirst) && (second <= endOfSecond)) { if(c[first] <= c[second]) d[result++] = c[first++]; else d[result++] = c[second++]; } //consider the rest if (first > endOfFirst) { //second paragraph left for(int q = second;q <= endOfSecond;q++) d[result++] = c[q]; } else { for(int q = first;q <= endOfFirst;q++) d[result++] = c[q]; } }
🥕 Onestep merge implementation
Merge adjacent segments whose size is segmentSize, and realize the process:
template<class T> void mergePass(T x[],T y[],int segmentSize,int n) { int i = 0; while(i <= n2*segmentSize) {//Merge two adjacent segments of size segmentSize merge(x,y,i,i+segmentSize1,i+2*segmentSize1); i = i+2*segmentSize; } //There are less than 2*segmentSize elements left if(i+segmentSize < n) merge(x,y,i,i+segmentSize1,n1); else for(int j = i;j <= n1;j++) y[j] = x[j];//copy the last paragraph to y }
🥕Merge sort mergeSort implementation
template<class T> void mergeSort(T a[],int n) {//Sort a[0:n1] using the merge sort algorithm T*b = new T[n]; int segmentSize = 1;//segment size while(segmentSize < n) { mergePass(a,b,segmentSize,n);//merge from a to b segmentSize += segmentSize; mergePass(b,a,segmentSize,n);//merge from b to a segmentSize += segmentSize; } }
🐇Merge sort complexity analysis
 Space complexity: O(n)
 Time complexity: O(nlogn)
 Merge times: l o g 2 n log_2n log2n
 Merge sort is stable
📚Quick Sort
🐇Basic idea of quick sort

Take a number from the sequence as the base number

Partition
 Put all numbers larger than this number to the right of it
 All numbers less than or equal to it are placed to its left

Repeat the second step for the left and right intervals until there is only one number in each interval
🐇Quick sort implementation code
Quick Sort Application in Experiment 13
void Sort(node *array,int low,int high)//to sort { if(low > high) return;//Scheduled, not working int i,j; node index; node index; index = array[low];//Define the base number i = low; j = high; while(i < j) { while(i < j && array[j].weight >= index.weight) { //Find the number smaller than the reference number from right to left j; } if(j > i) { //Exchange array[i] and array[j], and move i one bit to the right array[i++] = array[j]; } while(i < j && array[i].weight < index.weight) { //From left to right, find the one that is larger than the base number i++; } if(j > i) { //Exchange array[i] and array[j], and shift j to the left array[j] = array[i]; } } array[i] = index;//Datum point homing Sort(array,low,i1);//Recursively call quicksort for elements smaller than the reference point Sort(array,i+1,high);//Recursively call quicksort for elements larger than the reference point }
🐇Quick sort complexity analysis
🥕 Space Complexity
Recursive stack space: O(n)
🥕Time complexity
 Worst case: the pivot element is the minimum or maximum element in the array, left is always empty (or right is always empty), time O( n 2 n^2 n2)
 Best case: the number of elements in left and right is roughly the same, time O(nlogn)
 Average complexity O(nlogn)
🥕Median Quick Sort
The median quicksort algorithm has better average performance.
 It is not necessary to use a[leftEnd] as the base number
 Take the element whose size is in the middle among {a[leftEnd], a[(leftEnd +rightEnd)/2], a[rightEnd]} as the reference number.
🔑 Reference blog