Easy Tutorial
Union Find Quick Union Find Compress Heap Index Shell Sort Merge Sort Binary Search Remove Heap Shift Down Heap Sort Union Find Quick Merge Graph Theory Short Path Graph Theory Deep Union Find Basic Binary Search Feature Insertion Sort Binary Search Tree Search Sorting Algorithm Derivative Problem Heap Storage Binary Search Tree Insert Heap Shift Up Binary Search Traverse Data Structures Tutorial Graph Theory Iter 2Way Quick Sort Binary Search Tree Random Quick Sort Graph Theory Union Find Rank Graph Theory Path 3Way Qiuck Sort Union Find Size Heap Sort Optimization Binary Search Level Traverse
❮ Binary Search Tree Search Heap Storage ❯

Sorting Algorithm Derivative Problems

This subsection summarizes the sorting algorithms in this tutorial.

(1) Both Merge Sort and Quick Sort use the Divide and Conquer algorithm.

As the name suggests, it involves dividing the original problem into sub-problems of the same structure, and then solving these sub-problems one by one. Once the sub-problems are solved, the original problem is also resolved.

(2) Definition of Inversions

If there exist positive integers i, j such that 1 ≤ i < j ≤ n and A[i] > A[j], then the ordered pair <A[i], A[j]> is called an inversion of A. We can use the merge idea from this tutorial to count the number of inversions.

(3) Finding the nth Largest Element in an Array

It is not necessary to sort the entire array. Using the idea of Quick Sort, the algorithm complexity for finding the nth largest element in an array is O(n).

❮ Binary Search Tree Search Heap Storage ❯