3.6

4.1 ComparisonSorts

• 1/2N^2 < NlgN (2<N<4);
• 判断Inversion - partially sorted -;

Inversion

Swap

adjacent相邻的；primitives

• randomly swap;
• stable/unstable;
• BinarySearch the site where x should be """ int temp = a[j] a[j]=a[j-1] temp =a [i] """ *number of inversions fixed per swap
  • insert sort
  • selection sort
  • merge sort