SPOJ "It's a murder!" challenge I wrote a solution for SPOJ "It's a murder!". I'm exceeding the time limit even after n log(n) solution and fast I/O.

Given a list of numbers, I need to calculate the sum of the sum of the previously encountered numbers that are smaller than the current number.  For example, given 1 5 3 6 4, the answer is

(0) + (1) + (1) + (1 + 5 + 3) + (1 + 3) = 15

My code has complexity n log(n) and is pretty much similar to how we calculate the number of inversions. The function merge in the code below merges two sorted arrays and the function merge_sort is the basic call to merge sort procedure. The array sum1 stores the cumulative sum in array1 of elements whose index is strictly less less that current index . The variable ans stores the final answer. How can I make my code more efficient ?

#include &lt;bits/stdc++.h&gt;
using namespace std ; 

//Declaration of global variables
int array[100000] , array1[100000] , array2[100000]   ; 
long long int sum1[100000] ;
long long int ans ; 

void merge_sort(int left , int right) ; 
void merge(int left , int mid , int right) ; 

int main()
{
    int t,counter,n,i ;

    // t is the number of testcases
    scanf("%d",&amp;t) ;  

    for(counter=0;counter&lt;t;counter++)
    {
        // n is the number of elements in the array
        scanf("%d",&amp;n) ; 

        for(i=0;i&lt;n;i++)
        {
            scanf("%d",&amp;array[i]) ;

        }

        // ans hold the final answer and so it is initialized to 0 for every test case
        ans =0 ; 
        merge_sort(0 , n-1) ; 


        printf("%lld\n",ans );

    } 

}

void merge(int left , int mid , int right)
{
    int  index , index1 , index2 ;

     // array1 is used to store the elements from left to mid
     // array2 is used to store the elemetns from mid+1 to right
     // sum1 holds the sum of elements whose index is less than current index in array1 so that sum1[0] is always 0 .       

     // sum1 is initialised to 0
     memset(sum1,0,sizeof(sum1)) ; 

    // copying into array1 from left to mid 
    index1 = 0 ; 
    for(index=left;index&lt;mid+1;index++)
    {
        if(index1!=0)
        {
            sum1[index1] = sum1[index1-1] + array1[index1-1] ; 
        }

        array1[index1] = array[index] ; 
        index1++ ; 
    } 

    // copying into array2 from mid+1 to right
    index2 = 0;
    for(index=mid+1;index&lt;right+1;index++)
    {

        array2[index2] = array[index] ; 
        index2++ ; 
    }


    //merging the two arrays array1 and array2 and adding to the variable  ans array[index1] if array1[index1] &lt; array2[index2]
    index1 = 0 ; 
    index2 = 0 ; 
    index = left ; 
    while((index1&lt;mid-left+1)&amp;&amp;(index2&lt;right-mid))
    {
        if(array1[index1]&lt;array2[index2])
        {

            array[index] = array1[index1] ; 
            index++ ; 
            index1++ ; 
        }
        else if(array1[index1]&gt;=array2[index2])
        {
            ans = ans + sum1[index1];
            array[index] = array2[index2] ; 
            index++ ; 
            index2++ ; 
        }

    }

    if(index1&lt;mid-left+1)
    {
        while(index1&lt;mid-left+1)
        {
            array[index] = array1[index1] ; 
            index++ ; 
            index1++ ; 
        }
    }
    else if(index2&lt;right-mid)
    {
        while(index2&lt;right-mid)
        {
            ans = ans + sum1[index1-1] + array1[index1-1];
            array[index] = array2[index2] ; 
            index++ ; 
            index2++ ; 
        }
    }
}

void merge_sort(int left , int right)
{
    // Typical merge sort procedure
    if(left==right)
    {

    }
    else
    {
        int mid = (left+right)/2 ; 
        merge_sort(left , mid) ; 
        merge_sort(mid+1 , right) ; 
        merge(left , mid , right) ; 
    }
}
Your main issue is this line:

 memset(sum1,0,sizeof(sum1)) ;


The whole array is being initialized to zero, even if you are only dealing with a range of one element.  You really only need to initialize the first element:

sum1[0] = 0; // initialize here

// copying into array1 from left to mid 
index1 = 0 ;
for(index=left;index&lt;mid+1;index++)
{
    if(index1!=0)
    {
        sum1[index1] = sum1[index1-1] + array1[index1-1] ;
    }


The rest is already assigned proper values.