Insertion Sort @ InterviewStreet

Problem Links:

Interviewstreet,

Problem:

Insertion Sort (25 Points)

Insertion Sort is a classical sorting technique. One variant of insertion sort works as follows when sorting an array a[1..N] in non-descending order:

for i  = 2 to N    j = i   while j > 1 and a[j] < a[j - 1]        swap a[j] and a[j - 1]
        j = j-1 

The pseudocode is simple to follow. In the ith step, element a[i] is inserted in the sorted sequence a[1..i - 1]. This is done by moving a[i] backward by swapping it with the previous element until it ends up in it's right position.

As you probably already know, the algorithm can be really slow. To study this more, you want to find out the number of times the swap operation is performed when sorting an array.

Input:
The first line contains the number of test cases T. T test cases follow. The first line for each case contains N, the number of elements to be sorted. The next line contains N integers a[1],a[2]...,a[N].

Output:
Output T lines, containing the required answer for each test case.

Constraints:

1 <= T <= 5
1 <= N <= 100000
1 <= a[i] <= 1000000

Sample Input:
2
5
1 1 1 2 2
5
2 1 3 1 2

Sample Output:
0
4 

---

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * This problem actually ask the coder to count the number of inversions.
 * The updated merge-sort could count this number perfectly.
 */

/**
 * @author antonio081014
 * @since Jan 8, 2012, 4:41:26 PM
 */
public class Solution {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(
        // new DataInputStream(new FileInputStream("input.txt"))));
        // BufferedWriter bw = new BufferedWriter(new FileWriter(new File(
        // "output.txt")));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            int[] nums = new int[N];
            String[] strs = br.readLine().split(" ");
            for (int j = 0; j < N; j++)
                nums[j] = Integer.parseInt(strs[j]);
            System.out.println(Long.toString(sort_and_count(nums, 0, N - 1)));
            // bw.write(Long.toString(sort_and_count(nums, 0, N - 1)) + "\n");
        }
        // br.close();
        // bw.close();
    }

    public static long sort_and_count(int[] a, int x1, int x2) {
        if (x2 <= x1)
            return 0L;
        if (x2 == x1 + 1) {
            if (a[x1] > a[x2]) {
                a[x1] ^= a[x2];
                a[x2] ^= a[x1];
                a[x1] ^= a[x2];
                return 1L;
            }
            return 0L;
        }
        int mid = (x2 + x1) / 2;
        long count = 0L;
        count += sort_and_count(a, x1, mid);
        count += sort_and_count(a, mid + 1, x2);
        count += merge_and_count(a, x1, mid, mid + 1, x2);
        return count;
    }

    public static long merge_and_count(int[] a, int x1, int x2, int y1, int y2) {
        long count = 0L;
        for (int i = x1, j = y1; i <= x2 && j <= y2;) {
            if (a[i] > a[j]) {
                count += (long) (x2 - i + 1);
                j++;
            }
            else
                i++;
        }
        Arrays.sort(a, x1, y2 + 1);
        return count;
    }

    public static long insertSort(int[] a) {
        long count = 0;
        for (int i = 1; i < a.length; i++) {
            int j = i;
            while (j >= 1 && a[j] < a[j - 1]) {
                a[j] ^= a[j - 1];
                a[j - 1] ^= a[j];
                a[j] ^= a[j - 1];
                count++;
                j--;
            }
        }
        return count;
    }
}