# Pastebin VMbUPrVu
def insert(array)
    if array.length == 1
        return array
    elsif array.length == 2
        if array[0] <= array[1]
            return [array[0], array[1]];
        else 
            return [array[1], array[0]];
		end
    else
        k = (array.length / 2).floor
        left = array[0..k]
        right = array[k..array.length]
		left = insert(left);
		right = insert(right);
		i,j,newArray = 0,0,[] of Int32
        while i < left.length || j < right.length
            if left[i] <= right[j]
                if i < left.length
                    newArray.push(left[i]);
                    i+=1
				else
                    newArray.push(right[j]);
                    j+=1
				end
            else
                if j < right.length
                    newArray.push(right[j]);
                    j+=1
                else
                    newArray.push(left[i]);
                    i+=1
				end
			end
		end
        newArray
	end
end


puts insert([1,5,8,3,9,2,5])