Sort | Learn for Master
• ### Java Sort using Comparable or Comparator

In Java, it is straightforward to sort objects of the predefined class such as Integer, Double, Float and String. This is because these classes have been implemented the Comparable interface.  Comparable defines a natural ordering, as when you’re defining it, you specify which one is  considered “less than” or “greater than” the another.

How can you sort custom Objects? For example, suppose you have a list of objects of Student class, which has name, age, and score attributes. You may want to sort the students by their scores. Another example is to sort a list strings by their length.

• ### Quicksort algorithm

Quicksort is one of the most famous sort algorithms because of its average good performance. Because of its importance and popularity, it is usually asked in technique interviews. It is also important to master QuickSort as its partitioning technique can also be used to find the Kth largest or smallest element of an array in O(n) time with O(1) space complexity.

How quickSort algorithm works

Given an array A[s … e], a pivot is chosen to rearrange the array into two parts: ALeft and Aright. All the elements in ALeft are less than or equal to the pivot,

• ### LeetCode – Merge Sorted Array without extra space

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Analysis

We have described how to merge two sorted arrays into a third sorted array. For this problem, as A is assumed to have enough space, we are not allowed to create a third array.

We cannot start the merge from the beginning of the two arrays,

• ### Merge two sorted arrays algorithm (Java)

Given two sorted arrays or lists, how to merge them into a sorted array?

This is a fundamental problem as it is a common requirement to merge two sorted arrays into one sorted array. The algorithm of merging two sorted arrays is also the basics of the one of the most famous sort algorithms: merge sort.

Suppose there are two sorted arrays A and B, and we want to merge them into a third Array C.

We define three indexes a, b, c, which points to the beginning of the three arrays A, B,

• ### Leetcode – Color Sort

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s,