言語選択

一昨日codeforcesで開催された問題を昨日解いていたのですが。
Haskellで書いたものはタイムオーバーになってしまいました。

問題はこちら

模範解答？のようなものがcodeforcesに挙げられていたので読んでみた
すると、私が考えた通り、aの要素でソートしてからb要素の比較をするらしい。
Haskellで書いてみたものがこちら

import Data.List

main = do n <- getLine
          ab <- getContents
          let ab_s = sort.map ((\[a,b]->(read a,read b)).words)
                        .take (read n) $ lines ab
          print $ answer (snd $ head ab_s) $tail ab_s

answer :: Int->[(Int,Int)] -> Int
answer _ [] = 0
answer d ((_,b):ab) = if d > b
                        then 1+answer d ab
                        else answer b ab

素直にそのまま書いてます。
ところがこれでは、先に述べたように、入力数の多いものに対し、2000ms以上かかりタイムオーバーです。
ちょっとアルゴリズムの改良法が思いつかなかったので、
C言語で同様のものを書いてみた。

#include<stdio.h>
#define N 100000

int data[N][2];

void Swap(int i,int j){
	int temp1,temp2;
	temp1 = data[i][0];
	temp2 = data[i][1];
	data[i][0] = data[j][0];
	data[i][1] = data[j][1];
	data[j][0] = temp1;
	data[j][1] = temp2;
}

void sort(int left,int right){
	int i,j,pivot;
	i = left;
	j = right;
	pivot = data[(left+right)/2][0];
	
	while(1){
		while(data[i][0] < pivot)
			i++;
		while(pivot < data[j][0])
			j--;
		if(i >= j)
			break;
		Swap(i,j);
		i++;
		j--;
	}
	
	if(left < i-1)
		sort(left,i-1);
	if(j+1 < right)
		sort(j+1,right);
}

int main(){
	int rg,i,n,answer;
	answer = 0;
	scanf("%ld",&n);
	
	for(i = 0 ; i < n ; i++){
		scanf("%d %d\n",&data[i][0],&data[i][1]);
	}
	sort(0,n-1);
	
	rg = data[0][1];
	for(i = 0 ; i < n ; i++){
		if(rg > data[i][1])
			answer++;
		else
			rg = data[i][1];
	}
	printf("%d",answer);
	return 0;
}

なんとこちらは、たったの130ms、全問クリアでAcceptedです。
早っ！なぜ！

もしかしてHaskellのsortに問題があるんじゃないだろうか

なので、クイックソートにその部分のみ書き換えて実行してみた。
が、それでもやはりタイムオーバーになってしまった。

うーん、ソートが原因ではないのだろうか....
解けはしたけど、腑に落ちない