“This is the 11th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

Follow me for more updates

Data structure and algorithm (I): time complexity and space complexity

Data structure and algorithm (2): stack

Data structure and algorithm (3): queue

Data structure and algorithm (4): single linked list

Data structure and algorithm (5): two-way linked list

Data structure and algorithm (6): hash table

Data Structures and algorithms (7): trees

Data Structure and algorithm (8): sorting algorithm

Data Structures and algorithms (9): classical algorithm interview questions

Introduction to merge sort

Merge sort is an efficient sorting algorithm based on merge operation. It is a typical application of divide and conquer. Merge sort, first of all the elements of an array of binary split, in turn until you can’t break up, then two mergers in the correct order for the orderly sequence, and then put the orderly sequence continue two merged, until the final merger, get a complete and orderly sequence. So the idea of merge sort is to gradually merge the subsequences that are already ordered, to get a completely ordered sequence. (Merging two ordered tables into a single ordered table is called a two-way merge.)

Merge sort really does two things: decompose and merge

(1) “decomposition” — dividing the sequence in half at each fold.

(2) “merge” — sort the divided sequence segments by merging them in pairs.

(1) Divide-and-conquer diagram

(2) Single-trip merge diagram

For example will,5,7,8 [4] and [5] two has ordered subsequence, combined for the final sequence,2,3,4,5,6,7,8 [1]

Merge sort can be implemented in two ways: recursion-based merge sort and looping merge sort (also called top-down merge sort and bottom-up merge sort). Both recursion-based and looping merge sorts call the same core method: the algorithm that completes a single merge, that is, two already ordered array sequences are merged into a larger ordered array sequence.

Recursive implementation of merge sort

Recursion-based merge sort is also called top down merge sort.

Principle: When using the recursive method to implement merge sort, the core idea is to merge two ordered subsequence, notice that this is the ordered subsequence merge, so the following two things to do, the whole process is shown below:

(1) Divide the sequence to be sorted into two parts in the middle, and perform recursive segmentation on the left and right sides to get N independent subsequences; (2) Recursively merge n independent sub-sequences, and finally get the ordered sequence.

// mergeSort:(NSArray*) mergeSort:(NSArray*)arr{if (arr.count<=1) {return [arr mutableCopy]; Int center = (int)arr.count/2; NSArray*left = [arr subarrayWithRange:NSMakeRange(0, center)]; NSArray*right = [arr subarrayWithRange:NSMakeRange(center, arr.count-center)]; NSArray*leftSub = [self mergeSort:left]; NSArray*rightSub = [self mergeSort:right]; Return [self mergeLeft:leftSub right:rightSub]; }Copy the code
// mergeLeft (NSArray*)left right (NSArray*)right{NSMutableArray*result = [NSMutableArray array]; // mergeLeft (NSArray*)left right (NSArray*)right{NSMutableArray*result = [NSMutableArray array]; int i = 0; int j = 0; while (i<left.count && j<right.count) { if ([left[i] intValue] < [right[j] intValue]) { [result addObject:left[i]]; i++; }else { [result addObject:right[j]]; j++; } } while (i<left.count) { [result addObject:left[i]]; i++; } while (j<right.count) { [result addObject:right[j]]; j++; } return result.copy; }Copy the code

The terminating condition for recursion is that the length of the subsequence is 1, because having 1 elements is ordered by default

The core code is as follows:

NSArray*leftSub = [self mergeSort:left]; NSArray*rightSub = [self mergeSort:right]; Return [self mergeLeft:leftSub right:rightSub];Copy the code

Disadvantages of the recursive approach: each merge must create a temporary array that will hold the sorted subsequence until it is fully sorted. The space complexity of the whole merge sort process is order n.

Merge sort performance

Merge sort is a stable sort, it’s also a very efficient sort, it takes advantage of the full binary tree feature. Merge sort is O(nlog2n) in best, worst, and average time, and O(n) in space.

Other sorting algorithms

Sorting algorithm :1) Direct insertion sort

Sorting algorithm :2) Hill sort

Sorting algorithm :3) Bubble sort

Sorting algorithm :4) quick sort

Sorting algorithm :5) select sorting

Sorting algorithm :6) merge sort

Sorting algorithm :7) radix sort

Sorting algorithm :8) heap sort