Algorithm and Data Structure Basics  Sorting
Reference List

Introduction to Algorithms (Third Edition/Chinese Version), written by Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest and Clifford Stein, and translated by Jianping Yin, Yun Xu, Gang Wang, Xiaoguang Liu, Ming Su, Hengming Zou and HongZhi Wang.

Data Structures and Algorithms in Java (Second Edition/Chinese Version), written by Robert Lafore, and translated by Xiaoyun Ji, Yan Zhao, Xi Zeng and Xiaohan Di.
Terminology & Runtime Analysis
This part serves as a reading note for Introduction to Algorithms (Third Edition), Chapter 1 and Chapter 2, to clarify some basic terms of Algorithms.
Algorithm
is the process of reading a value or a collection of value as input, and product a value or a collection of value as output.
A sequence of input (with constrains) from a algorithm question is called a instance
of that question.
Runtime Analysis
From the book Introduction to Algorithms, the reason we are focusing on worst case running time is:

The worst running time gives a upper limitation running time for any input.

For some special algorithms, users can easily get worst case, such as searching for record which may not exist in database.

There is lots of times that the average running time is the same as the worst running time.
Basic Insertion Sort, with Analysis for Algorithm Questions
Insertion sort is very useful for a small amount of input.
In book Introduction to Algorithms, insertion sort is described as the same process of someone sorting a group of pokers in a poker game. All elements on one side of your current item (i.e. the item that is supposed to be sorted) is in order.
Pseudocode for Insertion Sort:
/* * In following code, left side of key is always being sorted, in acceding order. * In comparing process, starting from the element on the left of key, then moving towards start of array. */ for j=2 to A.length key = A[j] i = j1 //This loops means all sorted elements begin to move one space to end of array, so that key can be inserted to gap while i>0 and A[i] > key A[i+1] = A[i] i = i1 A[i+1] = key
Basic Selection Sort
To perform selection sort, you are given a array of numbers: A
.

You find the smallest element in A, then exchange this element with the element in A[0]

Starting from A[1], find the smallest element then changing with A[1]

Continue this process until you reach A[A.length1]
Code in Java:
public void selectionSort(int[] A){ int out, in, min; for(out=0; out<A.length1; out++){ min = A[out]; for(in=out+1; in<A.length; in++){ if(a[in]<min) min = a[in]; swap(A[out], min); } } }
Basic Merge Sort
Merge sort uses divideandconcur
mode:

Divide original question to smaller questions. For each subquestion, it is a instance of original question.

Solution these subquestions by using
recursion
. When the subquestion is small enough, solve this subquestion. 
Concur/Merge these subsolutions to the solution of original question.
The process of merge sort is:

Divide the array of
n
elements to two subarray. Each subarray should haven/2
elements. 
Recursively repeating the first step to subarrays until each subarray only have one element (i.e. Being sorted already).

Merge all sorted arrays to one sorted array.
The merge process is the key part of merge sort. From Introduction to Algorithms, A function merge(A, p, q, r)
can be used to perform merge process, where A
is the array, and p <= q <= r
. This process assumes that A[p:q]
and A[q+1:r]
has been sorted. At the end of merge process, A[p:r]
should be sorted.
In Introduction to Algorithms, a poker example is used to describe the merge process. The merge process is to chose a smaller one from the top of two piled poker, and put that poker to a new pile. Repeat this process until one pile is empty.
Since we most perform n
steps to merge, the running time of merge is $theta (n)$.
For Merge Sort in Java, please refer to this post.
Tips and Comments
 From Introduction to Algorithms, if you have a binary number, moving all digits one position to left means multiplying it by two. if you move all digits k position to left, you multiply origin number by $2^k$.
Other parts are working in process :)