Alignment algorithm (Merge Sort)

What is the mixing algorithm (Merge Sort)?

Mixing (Merge Sort) is an arrangement algorithm based on the Divide and Conquer algorithm. With the worst case time complexity of Ο (n log n), this is one of the algorithms that deserves the most attention.

First, the sort algorithm mixes to divide the array into two halves and then combine them into a sorted array.

Solution of mixing arrangement (Merge Sort) works

Here are illustrations of how the mixing algorithm works. Suppose we have the following array:

Alignment algorithm (Merge Sort) Picture 1

First, the sorting algorithm mixes the entire array into two halves. This division process continues until the division is no longer available and we obtain the corresponding values ​​representing the elements in the array. In the picture below, we first divide the array of size 8 into two size arrays 4.

Alignment algorithm (Merge Sort) Picture 2

This split process does not change the order of elements in the original array. Now we continue to divide these arrays into 2 halves.

Alignment algorithm (Merge Sort) Picture 3

Proceed to divide again until it is no longer divisible.

Alignment algorithm (Merge Sort) Picture 4

Now we combine them according to the way they are divided.

First we compare the two elements in each list and then combine them into another list in a sorted manner. For example, 14 and 33 are in sorted positions. We compare 27 and 10 and in the other list we place 10 at the beginning and then 27. Similarly, we change the positions of 19 and 35. 42 and 44 are placed respectively.

Alignment algorithm (Merge Sort) Picture 5

The next loop is to combine each of the above list pairs. We compare the values ​​and then merge them into a list containing 4 values, and these 4 values ​​are already ordered.

Alignment algorithm (Merge Sort) Picture 6

After the final merging step, the list will look like this:

Alignment algorithm (Merge Sort) Picture 7

The next section explores some other aspects of the mixing algorithm.

Algorithm for Mix Sort (Merge Sort)

The mixing arrangement algorithm continues the process of dividing the list into two halves until it cannot be divided. By definition, a list that has only one element, this list is considered sorted. Then, the sort algorithm mixes the sorted list together to form a new list that has also been sorted.

 Bước 1 : Nếu chỉ có một phần tử trong list thì list này được xem như là đã được sắp xếp. Trả về list hay giá trị nào đó. Bước 2 : Chia list một cách đệ qui thành hai nửa cho tới khi không thể chia được nữa. Bước 3 : Kết hợp các list nhỏ hơn (đã qua sắp xếp) thành list mới (cũng đã được sắp xếp).

Sample algorithm for mixed sort (Merge Sort)

It can be said that with the mixing algorithm, you need to pay attention to two main points: division and matching.

Because mixed sorting algorithms work recursively, we should use recursion to represent.

 B ắ t đầ u gi ả i thu ậ t s ắ p x ế p tr ộ n mergesort ( bi ế n a l à m ộ t m ả ng ) if ( n == 1 ) return a khai b á o bi ế n l1 l à m ộ t m ả ng = a [ 0 ] . a [ n / 2 ] khai b á o bi ế n l2 l à m ộ t m ả ng = a [ n / 2 + 1 ] . a [ n ] l1 = mergesort ( l1 ) l2 = mergesort ( l2 ) return merge ( l1 , l2 ) // gọi hàm merge() K ế t th ú c gi ả i thu ậ t B ắ t đầ u h à m merge ( M ả ng a , m ả ng b ) khai b á o bi ế n c l à m ộ t m ả ng while ( a v à b c ó ph ầ n t ử ) if ( a [ 0 ] > b [ 0 ] ) Th ê m b [ 0 ] v à o cu ố i m ả ng c X ó a b [ 0 ] t ừ b else Th ê m a [ 0 ] v à o cu ố i m ả ng c X ó a a [ 0 ] t ừ a k ế t th ú c if k ế t th ú c while while ( a c ó ph ầ n t ử ) Th ê m a [ 0 ] v à o cu ố i m ả ng c X ó a a [ 0 ] t ừ a k ế t th ú c while while ( b c ó ph ầ n t ử ) Th ê m b [ 0 ] v à o cu ố i m ả ng c X ó a b [ 0 ] t ừ b k ế t th ú c while return c K ế t th ú c h à m 

According to Tutorialspoint

Previous lesson: Selection sort algorithm (Selection Sort)

Next lesson: Shell Sort in data structure and algorithm