Progblemet #7 - sortering

Här kommer en variant av quick sort skrivet i Go. Den använder första elementet som avgränsare

func partition(arr []int) ([]int, []int) {
    pivot := arr[0]
    front := 1
    back  := len(arr) - 1

    for front <= back {
        if arr[front] < pivot {
            front++
        } else if (arr[back] >= pivot) {
            back--
        } else {
            arr[front], arr[back] = arr[back], arr[front]
        }
    }

    front--
    arr[0], arr[front] = arr[front], pivot
    return arr[:front], arr[back+1:]
}

func qsort(arr []int) {
    if len(arr) > 1 {
        lo, hi := partition(arr)
        qsort(lo)
        qsort(hi)
    }
}

func main() {
   arr := []int{3,4,1,2}
   qsort(arr)
   fmt.Println(arr)
}

Och en variant av merge sort i Go. Gjort det väldigt enkelt för mig och allokerar en temporär area som jag sätter ihop resultatet i sedan kopierar jag tillbaka det sorterade resultatet i ursprungs-arrayen.

func merge(result []int, a []int, b []int) {
    scratch := make([]int, len(result))
    ai := 0
    bi := 0
    for i := 0; i < len(result); i++ {
        if ai == len(a) {
            copy(scratch[i:], b[bi:])
            break
        } else if bi == len(b) {
            copy(scratch[i:], a[ai:])
            break
        } else {
            if a[ai] < b[bi] {
                scratch[i] = a[ai]
                ai++
            } else {
                scratch[i] = b[bi]
                bi++
            }
        }
    }
    copy(result, scratch)
}

func msort(arr []int) []int {
    if len(arr) > 1 {
        middle := len(arr) / 2
        merge(arr, msort(arr[:middle]), msort(arr[middle:]))
    }
    return arr
}

func main() {
    arr := []int{4,3,1,2}
    msort(arr)
    fmt.Println(arr)
}

Båda dessa är in-place sorting som är betydligt "snällare" mot CPU-cachen jämfört med om man skapat en ny array där (del)-svaret sparats. Vi kommer säkert få se varianter skrivna i funktionella språk som är betydligt enklare rent kod-mässigt än dessa, men dessa har tyvärr betydligt mycket sämre prestanda än in-place sorting.

Faktum är att din algoritm har O(N) som tidskomplexitet och på universitet får man ju lära sig att man ska bara titta på komplexitet och ignorera den konstanta termen, så detta måste ju vara en super-sorterare

Just konstanten gör att det faktiskt finns lägen när till och med bubble-sort kan vara vettig. Gjorde en Amiga-demo för länge, länge sedan och att implementera saker som quick-sort eller liknande i assembler är betydligt mycket mer komplicerat än bubble-sort. Bubble sort behöver bara 3 register, en för yttre loopen, en för inre loopen och en som pekar på det man sorterar. Så ska man sortera <=50-100 element så blir det svårt att slå bubble-sort.

Bubble-sort i Go, denna algoritm blir väldigt enkel i princip alla språk som tillåter "mutable" data.

func bubble_sort(arr []int) {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < i; j++ {
			if arr[j] > arr[j+1] {
                                arr[j], arr[j+1] = arr[j+1], arr[j]
                        }
                }
        }
}

Quick-sort i Haskell, denna kommer skapa massa kortlivade arrayer under sorteringen vilket gör den långsammare än Go versionen. Att dela upp elementen kommer i detta fall resultera i att man går igenom arrayen två gånger (två anrop till filter).

Men å andra sidan är denna väldigt enkel i kod!

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (pivot:xs) = (quicksort lo) ++ [pivot] ++ (quicksort hi)
    where
        lo  = filter (<= pivot) xs
        hi = filter (> pivot) xs

Quick-sort i Clojure, även den skapar massa kortlivade arrayer (vektorer) men tack vare group-by så kan man i alla fall dela upp elementen med en enda passering av arrayen.

(defn qsort[lst]
  (if (empty? lst)
    lst
    (let [pivot (first lst)
          parted (group-by (partial >= pivot) (rest lst))]
      (concat (qsort (parted true)) [pivot] (qsort (parted false))))))

Alltid kul att jämföra saker. Testar att variera två parametrar

1. storleken på arrayen som ska sorteras

2. maximala värdet på det slumptal som genereras

För Clojure använder jag detta, tiden som mäts är bara själva sorteringen

defn qsort[lst]
  (if (empty? lst)
    lst
    (let [pivot (first lst)
          parted (group-by (partial >= pivot) (rest lst))]
      (concat (qsort (parted true)) [pivot] (qsort (parted false))))))

(defn rand-seq[limit]
  (lazy-seq (cons (rand-int limit) (rand-seq limit))))

(doseq [sz [100000 1000000 10000000 2000000]
        limit [10000 1000000000]]
  (println "sz" sz " limit" limit)
  (let [arr (take sz (rand-seq limit))]
       (time (qsort arr))))

För Go kör jag detta, tar inte med Bubble sort mer än i fallet med 100k element då den skalar som O(N^2) så det skulle ta väldigt lång tid med 1M element,

package main

import (
        "fmt"
        "math/rand"
	"time"
)

func merge(result []int, a []int, b []int) {
        scratch := make([]int, len(result))
	ai := 0
	bi := 0
	for i := 0; i < len(result); i++ {
                if ai == len(a) {
                        copy(scratch[i:], b[bi:])
                        break
	        } else if bi == len(b) {
			copy(scratch[i:], a[ai:])
                        break
		} else {
                        if a[ai] < b[bi] {
	                        scratch[i] = a[ai]
                                ai++
        	        } else {
                                scratch[i] = b[bi]
                                bi++
                        }
        	}
        }
        copy(result, scratch)
}

func msort(arr []int) []int {
        if len(arr) > 1 {
	        middle := len(arr) / 2
                merge(arr, msort(arr[:middle]), msort(arr[middle:]))
        }
	return arr
}

func partition(arr []int) ([]int, []int) {
        pivot := arr[0]
        front := 1
	back  := len(arr) - 1

        for front <= back {
		if arr[front] <= pivot {
                        front++
	        } else if (arr[back] >= pivot) {
                        back--
        	} else {
                        arr[front], arr[back] = arr[back], arr[front]
                }
        }

        front--
        arr[0], arr[front] = arr[front], pivot
        return arr[:front], arr[back+1:]
}

func qsort(arr []int) {
	if len(arr) > 1 {
                lo, hi := partition(arr)
                qsort(lo)
	        qsort(hi)
        }
}

func bubble_sort(arr []int) {
        for i := 0; i < len(arr); i++ {
	        for j := 0; j < i; j++ {
	                if arr[j] > arr[j+1] {
	                        arr[j], arr[j+1] = arr[j+1], arr[j]
			}
	        }
	}
}

func rand_arr(cnt int, limit int) []int {
        arr := make([]int, cnt)
        for i := 0; i < cnt; i++ {
                arr[i] = rand.Intn(limit)
        }
        return arr
}

func do_timed(action func()) float64 {
        start := time.Now()
        action()
        end := time.Now()
        return end.Sub(start).Seconds()
}

func main() {
        k := 1000
        M := k * 1000
        szs := []int{ 100*k, 1*M, 10*M, 20*M }
        limits := []int{ 10*k, 1000*M }

        for _, sz := range(szs) {
                for _, limit := range(limits) {
                        fmt.Println("sz", sz, "limit", limit)
                        arr := rand_arr(sz, limit)

                        fmt.Print("Merge sort:\t")
                        a := make([]int, len(arr))
                        copy(a, arr)
                        fmt.Printf("%.2fs\n", do_timed(func() { msort(a) }))

                        fmt.Print("Quick sort:\t")
                        b := make([]int, len(arr))
                        copy(b, arr)
                        fmt.Printf("%.2fs\n", do_timed(func() { qsort(b) }))

                        if sz <= 100000 {
                                fmt.Print("Bubble sort:\t")
                                c := make([]int, len(arr))
                                copy(c, arr)
                                fmt.Printf("%.2fs\n", do_timed(func() { bubble_sort(b) }))
                        }
                }
                fmt.Println()
        }
}

Clojure:
Quick sort
100k element, 10k gräns -> 0.86s
100k element, 1000M gräns -> 0.51s
1M element, 10k gräns -> 12.5s
1M element, 1000M gräns -> 5.94s
10M element, 10k gräns -> orkar inte vänta så länge
10M element, 1000M gräns -> kraschar med GC overhead limit exceed

Go:
Quick sort
100k element, 10k gräns -> 0.01s
100k element, 1000M gräns -> 0.01s
1M element, 10k gräns -> 0.12s
1M element, 1000M gräns -> 0.10s
10M element, 10k gräns -> 5.06s
10M element, 1000M gräns -> 1.10s
20M element, 10k gräns -> 18.8s
20M element, 1000M gräns -> 2.28s

Merge sort
100k element, 10k gräns -> 0.02s
100k element, 1000M gräns -> 0.02s
1M element, 10k gräns -> 0.23s
1M element, 1000M gräns -> 0.23s
10M element, 10k gräns -> 2.48s
10M element, 1000M gräns -> 2.48s
20M element, 10k gräns -> 4.87s
20M element, 1000M gräns -> 5.34s

Bubble sort
100k element, 10k gräns -> 5.78s
100k element, 1000M gräns -> 5.77s

Notera att quick-sort är känslig för "dålig" input. När man genererar en array med som innehåller relativt många duplicerade värden så kommer quick-sort att bli O(log(N^2)) i de lägena att man har väldigt långa del-arrayer som innehåller samma eller några enstaka värden. Merge sort påverkar i princip inte alls av detta, men är å andra sidan långsammare när indata är "snällt"

Edit: systemet jag kört på är 64-bitars Ubuntu körandes på en Core i7 2760QM (2.4Ghz men när man bara använder en kärna brukar den hålla sig på 3.1GHz).

Well, beror lite på hur mycket man sträcker på sanningen. Bubble-sort och quick-sort är in-place helt och hållet, det enda jag jämfört mellan språk är quicksort.

Min Go merge-sort kan ses som in-place fast den kräver O(N) extra utrymme, i alla fall för någon som bara är användare av merge() funktionen då in-data och ut-data ockuperar samma minnesarea. Hade den inte varit in-place så hade merge skapat en ny array, vilket är klart enklare att resonera kring men blir långsammare på de CPUer vi har idag. Det går att göra en in-place merge av arrayer på O(1) extra utrymme, men i praktiken är det så pass komplicerat att det ofta blir billigare att allokera minne och sedan göra en kopiering på slutet.

Slutligen kring merge-sort: hade jag i stället sorterat listor så är merge-sort ofta ett väldigt bra val då det är trivialt att göra en in-place merge på O(1) utrymme om input är två listor.

Sedan försöker jag inte smutskasta funktionella språk, min avatar är ju loggan för Clojure som många anser var ett funktionellt språk (själv håller jag inte med, Lisp är inte funktionellt språk, man kan programmera funktionellt, men det kan man i språk som C,Go&C# också). Men den bistra sanningen är att dagens CPUer är byggda på ett sätt som gör att "mutable" strukturer och användning av variabler i stället för värden resulterar i betydligt mycket snabbare kod. För 6-7 år sedan trodda de flesta att funktionella språk skulle lösa problematiken kring hur man programmerar multi-core system (det är brutalt komplicerat om man använder sig av OOP och språk som C++, Java och C#). Och visst är det mycket enklare att programmera multi-core system i funktionella språk, men problemet är att resultatet blir långsamt och i många fall skalar det inte lika bra som vad är möjligt i C/C++.

Visst kan man använda sig av "mutable" i Clojure (det är inte ett funktionellt språk), men vad är poängen med att programmera Clojure då språkets stora styrka är att allt data ska vara ett värde (immutable) och gäller även vektorer/listor som är implementerade som persistent data structure (anses av många att vara den bästa implementationen av "persistent data structure" just nu)?

Det man insett är att problemet med att programmera multi-core system är inte "mutable"-state i sig, det är "mutable"-tillstånd som potentiellt kan refereras från mer än en CPU-kärna. Go är inte på något funktionellt, de som skapat språket ser det tvärt-om som ett modernt C. Men det Go har lagt till är möjligheten att väldigt enkelt kunna dela tillstånd mellan samtida trådar utan att för den delen direkt dela data (som är orsaken till race-buggar i multitrådade C, C++, Java och C# program). Inom en tråd är det inte mer komplicerat att hantera "mutable"-data än det var på 90-talet då vi bara hade en CPU-kärna.

Go, precis som Erlang, bygger på en grundfilosofi som kallas Communicating sequential processes (CSP), vilket betyder att saker delas endast genom att meddelade skickas mellan trådar/processer, inte genom att dela data och skydda data med lås.

Funktionella språk löste samma problem som Erlang/Go löser med meddelanden genom att garantera att data är ett värde (immutable), då behövs inga lås. Problemet är som sagt att sättet man skapar listor och andra former av strukturer blir relativt dyrt givet designen av dagens CPUer.

Tycker inte heller jag smutskastar funktionella språk genom att visa upp hur mycket enklare det är att skriva quicksort i t.ex. Haskell jämfört med Go. Men faktum kvarstår att ingen som skriver program med någon form av prestandakrav (i bemärkelsen lösa CPU-bundna problem) skulle komma på tanken att använda ett funktionellt språk. I vissa lägen är ändå funktionella språk en väldigt bra lösning, även om man har bråttom, kan ju finnas betydligt större flaskhalsar i systemet (*host* databaser, vilket då gör problemet I/O-bundet).

Körde motsvarande test på Java-koden nedan. Java var i begynnelsen ökänt för att vara långsamt, något som definitivt inte längre är sant. Sedan Java5 har ett typiskt Java-program kört snabbare än motsvarande C# program, i Java6/7 så har man gjort re-JIT och andra optimeringar än mer aggressiva. Resultatet är att Java ofta ligger på helt samma nivå som motsvarande C++, i vissa lägen kan det faktiskt vara snabbare.

Nackdelen med Java är programmen tenderar vara väldigt minneshungriga, se t.ex. detta där Java typiskt drar 2-20 gånger mer minne jämfört med Go som också är ett språk som använder sig av GC. Men då Java idag främst används på olika former av servers så är det kanske inte ett speciellt stort problem.

import java.util.Random;

class Sort {
    static void merge(int[] arr, int start, int middle, int end) {
        int len = end - start;
        int alen = middle - start;
        int blen = end - middle;
        int[] scratch = new int[len];
        int ai = 0;
        int bi = 0;
        for (int i = 0; i < len; i++) {
            if (ai == alen) {
                System.arraycopy(arr, middle + bi,
                                 scratch, i,
                                 len - ai - bi);
                break;
            } else if (bi == blen) {
                System.arraycopy(arr, start + ai,
                                 scratch, i,
                                 len - ai - bi);
                break;
            }
            if (arr[ai + start] < arr[bi + middle])
                scratch[i] = arr[start + ai++];
            else
                scratch[i] = arr[middle + bi++];
        }
        System.arraycopy(scratch, 0, arr, start, len);
    }

    static void msort(int[] arr, int start, int end)  {
        if (end - start > 1) {
            int middle = (end - start) / 2 + start;
            msort(arr, start, middle);
            msort(arr, middle, end);
            merge(arr, start, middle, end);
        }
    }

    static void mergeSort(int[] arr) {
        msort(arr, 0, arr.length);
    }

    static int partition(int[] arr, int left, int right) {
        int l = left + 1;
        int r = right;
        int pivot = arr[left];
        int tmp;

        while (l <= r) {
            if (arr[l] < pivot)
                l++;
            else {
                tmp = arr[l];
                arr[l] = arr[r];
        	arr[r] = tmp;
                r--;
            }
        }

        arr[left] = arr[r];
        arr[r] = pivot;

        return r;
    }

    static void qsort(int[] arr, int left, int right) {
        if (right - left > 1) {
            int pivotIdx = partition(arr, left, right);
            qsort(arr, left, pivotIdx - 1);
            qsort(arr, pivotIdx + 1, right);
        }
    }

    static void quickSort(int[] arr) {
	qsort(arr, 0, arr.length - 1);
    }

    static int[] randArr(int cnt, int limit) {
        Random r = new Random();
        int[] arr = new int[cnt];
        for (int i = 0; i < cnt; i++)
            arr[i] = r.nextInt(limit);
        return arr;
    }

    static double doTimed(Runnable action) {
        long start = System.nanoTime();
        action.run();
        long end = System.nanoTime();
        return (end - start) / 1_000_000_000.0;
    }

    public static void main(String []args) {
        int[] szs = new int[]{ 100_000, 1_000_000, 10_000_000, 20_000_000 };
        int[] limits = new int[]{ 10_000, 1_000_000_000 };

        for (int sz: szs)
            for (int limit: limits)
            {
                System.out.printf("sz %d  limit %d\n", sz, limit);
                int[] arr = randArr(sz, limit);

                System.out.print("Merge sort:\t");
                final int[] a = new int[arr.length];
                System.arraycopy(arr, 0, a, 0, arr.length);
                System.out.printf("%.2fs\n", doTimed(new Runnable() {
                        public void run() {
                            mergeSort(a);
                        } }));

                System.out.print("Quick sort:\t");
                final int[] b = new int[arr.length];
                System.arraycopy(arr, 0, b, 0, arr.length);
                System.out.printf("%.2fs\n", doTimed(new Runnable() {
                        public void run() {
                            quickSort(b);
                        } }));

            }
    }
}

Tyvärr kanske det kritiken att Java är ett "pratigt" språk stämmer, fast jämfört med Go (som har ett kortare program) så är det främst avsaknaden av array-slicing som komplicerar merge och partition. Array-siicing finns i språk som Python, Ruby och många andra skript-språk, men det saknas i populära språk som C, C#, Java och C++ (inte helt sant för C++, boost har slices).

Samma maskin som ovan. Java är i genomsnitt något snabbare än Go på merge-sort, men något långsammare på quck-sort. Go i sin tur ligger väldigt nära C/C++, så för sortering av heltal så kan man nog hävda att alla dessa språk leder till program som är ungefär lika snabba.

Java:
Quick sort
100k element, 10k gräns -> 0.02s
100k element, 1000M gräns -> 0.01s
1M element, 10k gräns -> 0.17s
1M element, 1000M gräns -> 0.11s
10M element, 10k gräns -> 9.48s
10M element, 1000M gräns -> 1.27s
20M element, 10k gräns -> 36.28s
20M element, 1000M gräns -> 2.64s

Merge sort
100k element, 10k gräns -> 0.04s
100k element, 1000M gräns -> 0.02s
1M element, 10k gräns -> 0.17s
1M element, 1000M gräns -> 0.16s
10M element, 10k gräns -> 1.72s
10M element, 1000M gräns -> 1.92s
20M element, 10k gräns -> 3.29s
20M element, 1000M gräns -> 3.86s

Tycker det så bra ut, mer eller mindre skolboksexempel. Finns dock en bugg i Quicksort som gör att den inte hanterar fall där man har duplikat av värden (blir evighetsloop).

Fixade den på detta sätt

template<typename T>
void Quicksort(T arr[], int n)
{
    if(n <= 1)
        return;
    int pivot_idx = rand() % n;
    int pivot = arr[pivot_idx];
    int l = 0;
    int r = n - 2;

    swap(arr[pivot_idx], arr[n-1]);
    while (l <= r)
    {
        if (arr[l] <= pivot)
     	    l++;
        else if (arr[r] > pivot)
            r--;
	else
            swap(arr[r], arr[l]);
    }
    swap(arr[l], arr[n-1]);

    Quicksort(arr, l);
    Quicksort(&(arr[l+1]), n - l - 1);
}

Noterade att du använder ett slumpmässigt pivot-tal. Det gör att man undviker O(N²) på saker som är sorterade baklänges, men det fixar ändå inte fallet där man har väldigt många tal som har samma värde.

Får följande värden på den dator jag kört alla andra tester på

Hela programmet är här

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <functional>
#include <vector>
#include <time.h>

using namespace std;

template<typename T>
void Insertionsort(T arr[], int n)
{
    T item;
    int j;
    for(int i = 1; i < n; i++){
	if(arr[i] < arr[i-1])
	{
            item = arr[i];
            j = i;
            while(j > 0 && item < arr[j-1])
            {
             	arr[j] = arr[j-1];
		j--;
            }
            arr[j] = item;
	}
    }
}


template<typename T>
void Selectionsort(T arr[], int n)
{
    int i, j, min;

    for(i = 0; i < n-1; i++)
    {
     	min = i;
	for(j = i+1; j < n; j++){
            if(arr[j] < arr[min])
		min = j;
	}
        swap(arr[i], arr[min]);
    }
}

template<typename T>
void Merge(T *arr, int left, int mid, int right)
{
    T *temp = new T[right-left+1];

    int pos = 0, lpos = left, rpos = mid+1;

    while(lpos <= mid && rpos <= right)
    {
        if(arr[lpos] < arr[rpos])
            temp[pos++] = arr[lpos++];
        else
            temp[pos++] = arr[rpos++];
    }
    while (lpos <= mid)
        temp[pos++] = arr[lpos++];
    while (rpos <= right)
        temp[pos++] = arr[rpos++];

    for(int i = 0; i < pos; i++)
    {
        arr[i+left] = temp[i];
    }
}

template<typename T>
void Mergesort(T arr[], int left, int right)
{
    int mid = (left + right)/2;

    if(left<right)
    {
        Mergesort(arr, left, mid);
        Mergesort(arr, mid+1, right);
        Merge(arr, left, mid, right);
    }
}

template<typename T>
void Quicksort(T arr[], int n)
{
    if(n <= 1)
        return;
    int pivot_idx = rand() % n;
    int pivot = arr[pivot_idx];
    int l = 0;
    int r = n - 2;

    swap(arr[pivot_idx], arr[n-1]);
    while (l <= r)
    {
        if (arr[l] <= pivot)
            l++;
        else if (arr[r] > pivot)
            r--;
        else
            swap(arr[r], arr[l]);
    }
    swap(arr[l], arr[n-1]);

    Quicksort(arr, l);
    Quicksort(&(arr[l+1]), n - l - 1);
}

vector<int> randArr(int cnt, int limit)
{
    vector<int> v(cnt);
    generate(begin(v), end(v), [=]() { return rand() % limit; });
    return v;
}

double doTimed(function<void()> action)
{
    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);
    action();
    clock_gettime(CLOCK_MONOTONIC, &end);
    if (end.tv_nsec < start.tv_nsec)
    {
        end.tv_sec  -= 1;
        end.tv_nsec += 1000000000;
    }

    return (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1000000000.0;
}

int main(int argc, char *argv[])
{
    auto szs = vector<int>{ 100000, 1000000, 10000000, 20000000 };                                    
    auto limits = vector<int>{ 10000, 1000000000 };                                                   

    cout << fixed << setprecision(2);
    for (auto sz: szs)
        for (auto limit: limits)
        {
            cout << "sz " << sz << " limit " << limit << endl;
            auto arr = randArr(sz, limit);

            cout << "Merge sort:\t";
            vector<int> a;
            copy(begin(arr), end(arr), back_inserter(a));
            cout << doTimed([&](){ Mergesort(a.data(), 0, a.size()); }) << endl;

            cout << "Quick sort:\t";
            vector<int> b;
            copy(begin(arr), end(arr), back_inserter(b));
            cout << doTimed([&](){ Quicksort(b.data(), b.size()); }) << endl;
       }

    return 0;
}

Använt lite C++11, som lambda och array-initializers. Dessa saker är helt klart ett lyft för C++

Ska sammanställa alla tider i ett Excel-ark och posta en länk till grafen, kanske inte händer i dag bara. Rent generellt verkar C++ ligga ungefär på samma nivå som Go och Java, vilket är precis vad man kan förvänta sig.

Edit: Merge sort tiderna var lite lustiga för C++, inser nu att Merge funktionen läcker minne, så det kan förklara varför programmet beter sig lite skumt. Saknas ett delete temp. Har uppdaterat tiderna.

Jämförelse mellan lite olika språk. Har normalisera värdena så att högre stapel är bättre. Den snabbaste har alltid värdet 1.0 och om det tog dubbel så lång tid får man värdet 0.5 o.s.v. Tider för 100k element kan man ignorera, det var så korta tider att mätningen inte blir vettig.

Visa innehåll

Dold text

C# koden är en direkt översättning från Java-koden. Testa också att göra en QuickSort som använde LINQ för uppdelningen, likt hur jag gjorde i Clojure. Det fungerar men blev tokslött, mycket långsammare än Clojure (typ 10-100 gånger långsammare). Här är LINQ varianten om någon vill testa

static IEnumerable<int> linqQsort(IEnumerable<int> arr)
    {
    if (arr.Count() <= 1)
        return arr;
    var pivot = arr.First();
    var rest = arr.Skip(1);
    return linqQsort(rest.Where(n => n <= pivot)).Concat(new int[]{pivot}.Concat(linqQsort(rest.Where(n => n > pivot))));
}

Här är hela C#-programmet

using System.Text;
using System.Threading.Tasks;

namespace progblemet7_sorting
{
    class Program
    {
        static void merge(int[] arr, int start, int middle, int end)
        {
            var len = end - start;
            var alen = middle - start;
            var blen = end - middle;
            var scratch = new int[len];
            var ai = 0;
            var bi = 0;
            for (var i = 0; i < len; i++)
            {
                if (ai == alen)
                {
                    Array.Copy(arr, middle + bi,
                               scratch, i,
                               len - ai - bi);
                    break;
                }
                else if (bi == blen)
                {
                    Array.Copy(arr, start + ai,
                               scratch, i,
                               len - ai - bi);
                    break;
                }
                if (arr[ai + start] < arr[bi + middle])
                    scratch[i] = arr[start + ai++];
                else
                    scratch[i] = arr[middle + bi++];
            }
            Array.Copy(scratch, 0, arr, start, len);
        }

        static void msort(int[] arr, int start, int end)
        {
            if (end - start > 1)
            {
                var middle = (end - start) / 2 + start;
                msort(arr, start, middle);
                msort(arr, middle, end);
        	merge(arr, start, middle, end);
            }
	}

        static void mergeSort(int[] arr)
        {
            msort(arr, 0, arr.Length);
        }


        static int partition(int[] arr, int left, int right)
        {
            var l = left + 1;
            var r = right;
            var pivot = arr[left];
            int tmp;

            while (l <= r)
            {
                if (arr[l] < pivot)
                    l++;
                else
                {
                    tmp = arr[l];
                    arr[l] = arr[r];
                    arr[r] = tmp;
                    r--;
                }
            }

            arr[left] = arr[r];
            arr[r] = pivot;

            return r;
        }

        static void qsort(int[] arr, int left, int right)
        {
            if (right - left > 1)
            {
                int pivotIdx = partition(arr, left, right);
                qsort(arr, left, pivotIdx - 1);
                qsort(arr, pivotIdx + 1, right);
            }
        }

        static void quickSort(int[] arr)
        {
            qsort(arr, 0, arr.Length - 1);
        }

        static int[] randArr(int cnt, int limit)
        {
            var r = new Random();
            var arr = new int[cnt];
            for (var i = 0; i < cnt; i++)
                arr[i] = r.Next(limit);
            return arr;
        }

        delegate void TimedAction();

        static double doTimed(TimedAction action) {
        var start = DateTime.Now;
        action();
        var elapsed = DateTime.Now - start;

        return elapsed.Seconds + elapsed.Milliseconds / 1000.0;
    }

        static void Main(string[] args)
        {
            var szs = new int[]{ 1000, 10000, 100000, 200000 };
            var limits = new int[]{ 10000, 1000000000 };

            foreach (var sz in szs)
                foreach (var limit in limits)
                {
                    Console.Out.WriteLine("sz {0}  limit {1}", sz, limit);
                    int[] arr = randArr(sz, limit);

                    Console.Out.Write("Merge sort:\t");
                    var a = new int[arr.Length];
                    Array.Copy(arr, 0, a, 0, arr.Length);
                    Console.Out.WriteLine("{0:F2}s", doTimed(() => mergeSort(a)));

                    Console.Out.Write("Quick sort:\t");
                    var b = new int[arr.Length];
                    Array.Copy(arr, 0, b, 0, arr.Length);
                    Console.Out.WriteLine("{0:F2}s", doTimed(() => quickSort(b)));
                }
        }
    }
}

Jag körde C# med Visual Studio 2012 på 64-bitars Win8 Pro. Testade även att köra Java-koden och den var väldigt nära samma program körandes på 64-bitars Linux, skilde typ 10% till Linux fördel. Så Java7 är faktiskt nära nog dubbelt så snabbt som .Net 5 just i detta fall. Säger inte att skillnaden är så stor alltid, men min erfarenhet är att Java6/7 har blivit rejält snabbt och är typiskt alltid lika snabbt eller snabbare än motsvarande C#/.Net program.

När jag såg din kommentar om IEnumerable så tänkte jag först: ah, du har rätt. Men sen började jag fundera, om det vore så visar det att MS totalt missförstått konceptet att frikoppla interface från konkret implementation. För varför skulle en array som implementerar IEnumerable inte ha ett Count() anrop som är O(1)???

Rent generellt kan man inte anta att Count() är O(1), i många fall kanske den faktiskt är O(N), men det finns ingen rimligt anledning varför den skulle vara det i mitt fall.

Skrev lite testkod där mäter kostnaden av att anropa Count() på en underliggande int[] och precis som jag misstänkte så är inte MS idioter. Det är en konstant-tid operation (och en extrem snabb sådan) i just detta fall.

Du har helt rätt i att man måste gå igenom arrayen två gånger när man använder Where(), min första implementation använde faktiskt GroupBy() just för att undvika detta men det var ännu långsammare.
Hur långsamt är det då? Att sortera 10k element tar ganska exakt 20s och äter ungefär 20M RAM....

Problemet verkar vara att LINQ skapar tusen och åter tusen små temporära objekt så GCn får slita ihjäl sig. LINQ är helt enkelt inte rätt verktyg här och det är nog just när folk testat att göra saker likt detta de har klagat på LINQ att leda till långsamma program. Och helt fel är inte kritiken, jag använder faktiskt samma angreppssätt i Clojure som ändå fixade 100k element på ungefär en halv sekund (så Clojure är närmare 1000 gånger snabbare än de 10-100 jag höftade till med ovan).
Personligen gillar jag dock LINQ skarpt, det är trots allt en riktigt trevlig Lisp feature i C#-smak!

Skulle vara väldigt intressant att se vad Scala presterar här och då med en implementation som är "bra" Scala och inte bara Java-implementation med Scala-syntax

Kan bli lite tid över någon kväll senare i veckan, ska titta på det då.

Men kom ihåg att jag inte är en C# expert. Håller mig mest uppdaterad kring .Net/C# för jag anser att det är en för stor/viktigt plattform att ignorera, men vare sig språk eller plattform är någon större favorit, hade därför totalt missat Stopwatch. Sedan står det att om man inte har en HPET i sin dator så använder Stopwatch DateTime internt, men jag har en HPET i denna dator med en upplösning på 1ns (är den som används för att mäta tiden i C++ versionen via clock_gettime()). Ska ändra till den, men då tiderna det handlar om här är 100-tals millisekunder upp till 10-tals sekunder så är jag rätt säker på att eventuellt mätfel i DateTime kan ignoreras

Visst är LINQ otroligt smidigt i vissa fall, men det är lite oroväckande när det är runt 1000 gånger långsammare än i princip samma logik skrivet i Clojure vars implementation i sin tur är runt 50 gånger långsammare än"mutable" varianterna i C++/C#/Java/Go. Skulle vara intressant att se hur Scala står sig om man kör med exakt samma logik där. Normalt sett är Scala-program snabbare än motsvarande Clojure, men Clojures implementation av "persistent data structures" är som sagt nog den bästa som går att hitta, vilket gör att hantering av containers som värden är relativt sett väldigt effektivt i Clojure.

Det är sant att metoderna för IEnumerable implementeras via "extensions methods" (i System.Linq.Enumerable), men polymorfism är möjligt även på "extensions methods" så det finns ingen anledning att förstöra information om typen då det dels skulle paja möjligheten till O(1) Count på t.ex. arrayer. Enligt både min black-box mätning (mätte tiden att en rad gånger köra Count() på arrayer med längden 10M, 100M, 1000M och 10000M) och enligt detta svar på stack-overflow så är Count() konstant tid om underliggande typ tillåter.

Mest för att avgränsa det lite. Men du har naturligtvis en poäng, kör man med listor så skulle t.ex. MergeSort blir både enklare och effektivare medan QuickSort skulle bli väldigt ineffektivt. Samma sak med InsertSort, blir ju en massa kopierande om man har en array medan det blir väldigt naturligt om man har listor (som att sortera in kort från vänster hand till ett sorterat set i höger hand).

Men med "rätt" algoritm så är det i princip alltid betydligt snabbare att sortera en array än att sortera en lista. Listor orsakar långt mycket fler minnesaccesser som nödvändigtvis inte ligger bredvid varandra i minne, vilket inte gillas av CPU-cache -> långsammare.

Hur man skulle använda Dictionary begriper jag inte riktigt. En sådan använder man för att mappa en nyckel till ett värde, vill man även att saker ska vara sorterade väljer man något form av självbalanserat träd.