空间复杂度
O(n) 需要辅助数组b[n]
时间复杂度
T(n)=O(1) if n=1
T(n)=2T(n/2) O(n) if n>=2
利用主方法求解T(n)=O(nlgn)
最坏情况和平均情况 O(nlgn) ----->递归深度lgn
最好情况 待排有序 O(n)
稳定性分析
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定 性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性。所以，归并排序是稳定的排序算法。
常规查找算法官方解释：查找(searching)是这样一个过程，即在某个项目组中寻找某一指定目标元素，或者确定该组中并不存在该目标元素。 -from 《java软件结构与数据结构》
线性查找 (linear search)线性查找算法是指当一个集合的数据杂乱无章的存放时，从第一个元素开始，将每个集合元素键值与待查找的元素的键值(能根据其对集合的数据进行排序)进行比较，直到找到或集合元素都已比较完毕为止。若待查找的元素在集合中存在，则停止查找；若待查找的元素根本就不存在于集合中，则集合中所有元素比较完之后，停止查找。
线性查找算法实现过程中数据结构的选取根据实际情况有所不同。集合中的数据可以存放于数组中，也可以存放于链表中，甚至其它的数据结构中。当算法思想是不变的，就是从第一个元素开始，逐一比较；因此，最差情况下，需要将所有元素比较一遍；尤其当集合中的数据量很大时，算法的运行时间就会明显降低，其与集合的数据量正相关。
它是最为常见、使用频率最高、程序中耗费时间最多的一种对数据的操作，是读取、插入、修改、删除等操作的基础。
原始数据：int[] a={4,6,2,8,1,9,0,3}; 要查找数字：8
