Sorting

The entire concept of the sorting problem is:

Given $n$ elements, rearrange them in ascending order.

In the next few sections, we will go over some algorithms, which does the following.

Merge Sort

Merge sort is an application of the divide-and-conquer principle. The basic approach is to:

  1. Divide the array into two halves.
  2. Sort each half recursively.
  3. Merge the two halves to make a sorted whole.

Figure 6.1a Example of merge sort.

Figure 6.1a Example of merge sort.

It uses a new array to store the merged array and scans the sub-array from left-to-right, storing elements in order — alphabetically in this case.

Figure 6.1b Example of merge sort.

Figure 6.1b Example of merge sort.

The beauty of merge sort is its efficiency. When compared to insertion sort, which has a time complexity of $O(N^2)$, merge sort has a time complexity of $O(N\log{N})$.

Figure 6.2 Efficiency between insertion sort and merge sort.

Figure 6.2 Efficiency between insertion sort and merge sort.

The efficiency and effectiveness of an algorithm can still be more important than raw computing power in many scenarios.

Quick Sort

Quick sort is another sorting algorithm based on the divide-and-conquer principle. It reduces the space complexity and removes the use of the auxiliary array that is used in merge sort.

  1. Pick a pivot element from array.