Merge sort and quick sort (32)

In the last section, we learned about bubble sorting and Hill sorting, and in this section we continue to learn about merge sorting and quick sorting.

1. Merge sorting: merge two or more ordered sequences into a new ordered sequence. As follows

Then since there are two ways to merge, there will be multiple ways to merge. Three ordered sequences are merged into a new ordered sequence, which is called 3-way merging; N ordered sequences are merged into a new ordered sequence, which becomes N-path merging; and multiple ordered sequences are merged into a new ordered sequence, which is called multipath merging.

Let's take a look at an example of a two-way merger, as shown in the following figure

Let's see how it is implemented, as shown below

It is compared one by one by comparing the size of the two sequences. Let's take a look at the specific implementation of merge sorting. The specific source code is as follows

# ifndef SORT_H#define SORT_H#include "Object.h" namespace DTLib {class Sort: public Object {private: Sort (); Sort (const Sort&); Sort& operator= (const Sort&); template static void Swap (T & a, T & b) {TC (a); a = b; b = c;} template

Static void Merge (T src [], T helper [], int begin, int mid, int end, bool min2max) {int I = begin; int j = mid + 1; int k = begin; while ((I