Pygments for Jekyll Sample - Emacs
- 2015-03-24 -
Merge sort in various languages using the Emacs theme.
Javascript
function merge_sort(arr) {
var l = arr.length, m = Math.floor(l/2);
if (l <= 1) return arr;
return merge(merge_sort(arr.slice(0, m)), merge_sort(arr.slice(m)));
}
function merge(left,right) {
var result = [];
var ll = left.length, rl = right.length;
while (ll > 0 && rl > 0) {
if (left[0] <= right[0]) {
result.push(left.shift());
ll--;
} else {
result.push(right.shift());
rl--;
}
}
if (ll > 0) {
result.push.apply(result, left);
} else if (rl > 0) {
result.push.apply(result, right);
}
return result;
}
Python
def mergesort(arr):
if len(arr) == 1:
return arr
m = len(arr) / 2
l = mergesort(arr[:m])
r = mergesort(arr[m:])
if not len(l) or not len(r):
return l or r
result = []
i = j = 0
while (len(result) < len(r)+len(l)):
if l[i] < r[j]:
result.append(l[i])
i += 1
else:
result.append(r[j])
j += 1
if i == len(l) or j == len(r):
result.extend(l[i:] or r[j:])
break
return result
Ruby
def mergesort(list)
return list if list.size <= 1
mid = list.size / 2
left = list[0, mid]
right = list[mid, list.size]
merge(mergesort(left), mergesort(right))
end
def merge(left, right)
sorted = []
until left.empty? or right.empty?
if left.first <= right.first
sorted << left.shift
else
sorted << right.shift
end
end
sorted.concat(left).concat(right)
end
Java
view plaincopy to clipboardprint?
public IList MergeSort(IList list)
{
if (list.Count <= 1)
return list;
int mid = list.Count / 2;
IList left = new ArrayList();
IList right = new ArrayList();
for (int i = 0; i < mid; i++)
left.Add(list[i]);
for (int i = mid; i < list.Count; i++)
right.Add(list[i]);
return Merge(MergeSort(left), MergeSort(right));
}
public IList Merge(IList left, IList right)
{
IList rv = new ArrayList();
while (left.Count > 0 && right.Count > 0)
if (((IComparable)left[0]).CompareTo(right[0]) > 0)
{
rv.Add(right[0]);
right.RemoveAt(0);
}
else
{
rv.Add(left[0]);
left.RemoveAt(0);
}
for (int i = 0; i < left.Count; i++)
rv.Add(left[i]);
for (int i = 0; i < right.Count; i++)
rv.Add(right[i]);
return rv;
}
Erlang
merge_sort(List) when length(List) =< 1 -> List;
merge_sort(List) ->
{Left, Right} = lists:split(length(List) div 2, List),
lists:merge(merge_sort(Left), merge_sort(Right)).
Objective C
-(NSArray *)mergeSort:(NSArray *)unsortedArray
{
if ([unsortedArray count] < 2)
{
return unsortedArray;
}
long middle = ([unsortedArray count]/2);
NSRange left = NSMakeRange(0, middle);
NSRange right = NSMakeRange(middle, ([unsortedArray count] - middle));
NSArray *rightArr = [unsortedArray subarrayWithRange:right];
NSArray *leftArr = [unsortedArray subarrayWithRange:left];
//Or iterate through the unsortedArray and create your left and right array
//for left array iteration starts at index =0 and stops at middle, for right array iteration starts at midde and end at the end of the unsorted array
NSArray *resultArray =[self merge:[self mergeSort:leftArr] andRight:[self mergeSort:rightArr]];
return resultArray;
}
-(NSArray *)merge:(NSArray *)leftArr andRight:(NSArray *)rightArr
{
NSMutableArray *result = [[NSMutableArray alloc] init];
int right = 0;
int left = 0;
while (left < [leftArr count] && right < [rightArr count])
{
if ([[leftArr objectAtIndex:left] intValue] < [[rightArr objectAtIndex:right] intValue])
{
[result addObject:[leftArr objectAtIndex:left++]];
}
else
{
[result addObject:[rightArr objectAtIndex:right++]];
}
}
NSRange leftRange = NSMakeRange(left, ([leftArr count] - left));
NSRange rightRange = NSMakeRange(right, ([rightArr count] - right));
NSArray *newRight = [rightArr subarrayWithRange:rightRange];
NSArray *newLeft = [leftArr subarrayWithRange:leftRange];
newLeft = [result arrayByAddingObjectsFromArray:newLeft];
return [newLeft arrayByAddingObjectsFromArray:newRight];
}
Swift
import Foundation
// Build 100 random numbers between 0 and 100
var numbers = Int[]()
for i in 1..100 {
let n = Int(arc4random() % 101)
numbers.append(n)
}
func elementsInRange<T>(a: T[], start: Int, end: Int) -> (T[]) {
var result = T[]()
for x in start..end {
result.append(a[x])
}
return result
}
func merge<T: Comparable>(a: T[], b: T[], mergeInto acc: T[]) -> T[] {
if a == [] {
return acc + b
} else if b == [] {
return acc + a
}
if a[0] < b[0] {
return merge(elementsInRange(a, 1, a.count), b, mergeInto: acc + [a[0]])
} else {
return merge(a, elementsInRange(b, 1, b.count), mergeInto: acc + [b[0]])
}
}
func mergesort<T: Comparable>(a: T[]) -> T[] {
if a.count <= 1 {
return a
} else {
let firstHalf = elementsInRange(a, 0, a.count/2)
let secondHalf = elementsInRange(a, a.count/2, a.count)
return merge(mergesort(firstHalf), mergesort(secondHalf), mergeInto: [])
}
}
let sorted = mergesort(numbers)
println(sorted)
C#
view plaincopy to clipboardprint?
public IList MergeSort(IList list)
{
if (list.Count <= 1)
return list;
int mid = list.Count / 2;
IList left = new ArrayList();
IList right = new ArrayList();
for (int i = 0; i < mid; i++)
left.Add(list[i]);
for (int i = mid; i < list.Count; i++)
right.Add(list[i]);
return Merge(MergeSort(left), MergeSort(right));
}
public IList Merge(IList left, IList right)
{
IList rv = new ArrayList();
while (left.Count > 0 && right.Count > 0)
if (((IComparable)left[0]).CompareTo(right[0]) > 0)
{
rv.Add(right[0]);
right.RemoveAt(0);
}
else
{
rv.Add(left[0]);
left.RemoveAt(0);
}
for (int i = 0; i < left.Count; i++)
rv.Add(left[i]);
for (int i = 0; i < right.Count; i++)
rv.Add(right[i]);
return rv;
}
C++
vector<int> merge_sort(vector<int>& vec)
{
// Termination condition: List is completely sorted if it
// only contains a single element.
if(vec.size() == 1)
{
return vec;
}
// Determine the location of the middle element in the vector
std::vector<int>::iterator middle = vec.begin() + (vec.size() / 2);
vector<int> left(vec.begin(), middle);
vector<int> right(middle, vec.end());
// Perform a merge sort on the two smaller vectors
left = merge_sort(left);
right = merge_sort(right);
return merge(left, right);
}