text:
Create a diagonal sudoku board
A Diagonal Sudoku board is a special case of Latin squares. It has the following properties:

The board is a 9-by-9 matrix
Each row contains the numbers 1-9
Each column contains the numbers 1-9
Each 3-by-3 sub-region contains the numbers 1-9
Both diagonals contains the numbers 1-9

Challenge:
Create a program or function that outputs a complete board with all 81 numbers that complies with the rules above.
The number in at least one position must be random, meaning the result should vary accross executions of the code. The distribution is optional, but it must be possible to obtain at least 9 structurally different boards. A board obtained from another by transliteration is not considered structurally different. Transliteration refers to substituting each number x by some other number y, consistently in all positions of number x.
Hardcoding 9 boards is not accepted either.
Rules:

Output format is optional, as long as it's easy to understand (list of list is OK)
The random number can be taken as input instead of being created in the script, but only if your language doesn't have a RNG.

This is code golf so the shortest code in bytes win!
Example boards:
7   2   5  |  8   9   3  |  4   6   1
8   4   1  |  6   5   7  |  3   9   2
3   9   6  |  1   4   2  |  7   5   8
-------------------------------------
4   7   3  |  5   1   6  |  8   2   9
1   6   8  |  4   2   9  |  5   3   7
9   5   2  |  3   7   8  |  1   4   6
-------------------------------------
2   3   4  |  7   6   1  |  9   8   5
6   8   7  |  9   3   5  |  2   1   4
5   1   9  |  2   8   4  |  6   7   3

4   7   8  |  1   9   5  |  3   2   6
5   2   6  |  4   8   3  |  7   1   9
9   3   1  |  6   7   2  |  4   5   8
-------------------------------------
2   5   9  |  8   6   7  |  1   3   4
3   6   4  |  2   5   1  |  9   8   7
1   8   7  |  3   4   9  |  5   6   2
-------------------------------------
7   1   2  |  9   3   8  |  6   4   5
6   9   3  |  5   2   4  |  8   7   1
8   4   5  |  7   1   6  |  2   9   3

Is there any limit to execution time?

It should ideally finish in less than a minute, but that's not a strict requirement. There's some leeway there, but you can't have a script running for hours.

SWI-Prolog, 438 bytes
:-use_module(library(clpfd)).
a(R):-l(9,R),m(l(9),R),append(R,V),V ins 1..9,transpose(R,C),d(0,R,D),maplist(reverse,R,S),d(0,S,E),r(R),m(m(all_distinct),[R,C,[D,E]]),get_time(I),J is ceil(I),m(labeling([random_value(J)]),R).
l(L,M):-length(M,L).
r([A,B,C|T]):-b(A,B,C),r(T);!.
b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-all_distinct([A,B,C,D,E,F,G,H,I]),b(X,Y,Z);!.
d(X,[H|R],[A|Z]):-nth0(X,H,A),Y is X+1,(R=[],Z=R;d(Y,R,Z)).
m(A,B):-maplist(A,B).

Returns the answer as a list of lists, e.g. a(Z) unifies Z with [[2, 3, 6, 4, 9, 8, 7, 1, 5], [4, 5, 9, 2, 1, 7, 8, 3, 6], [7, 8, 1, 5, 3, 6, 9, 2, 4], [3, 2, 8, 7, 6, 4, 5, 9, 1], [5, 1, 4, 9, 8, 2, 3, 6, 7], [9, 6, 7, 1, 5, 3, 4, 8, 2], [1, 9, 2, 3, 4, 5, 6, 7, 8], [8, 7, 5, 6, 2, 9, 1, 4, 3], [6, 4, 3, 8, 7, 1, 2, 5, 9]].
Explanation
:-use_module(library(clpfd)).          % Constraint Programming Library

a(R):-                                 % Main Predicate
    l(9,R),m(l(9),R),append(R,V),      % R is a list of 9 lists, each of length 9
    V ins 1..9,                        % Values in R are between 1 and 9
    transpose(R,C),                    % C is the transpose of R
    d(0,R,D),                          % D is the diagonal of R
    maplist(reverse,R,S),d(0,S,E),     % E is the anti-diagonal of R
    r(R),                              % All 3*3 blocks must contain numbers from 1 to 9
    m(m(all_distinct),[R,C,[D,E]]),    % Each row of R, each row of C, D and E must contain
                                       % only distinct numbers
    get_time(I),J is ceil(I),          % Set J to a random number based on the current time
    m(labeling([random_value(J)]),R).  % Randomly find a solution for R

l(L,M):-                               % L is the length of M
    length(M,L).

r([A,B,C|T]):-                         % For each group of 3 rows, the 3*3 blocks must
    b(A,B,C),r(T);!.                   % contain distinct numbers

b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-     % Checks that the 3 3*3 blocks of 3 rows have
                                       % distinct numbers inside them
    all_distinct([A,B,C,D,E,F,G,H,I]),
    b(X,Y,Z);!.

d(X,[H|R],[A|Z]):-                     % [A|Z] is the diagonal of [H|R]
    nth0(X,H,A),
    Y is X+1,
    (R=[],Z=R;d(Y,R,Z)).

m(A,B):-
    maplist(A,B).

APL (Dyalog Unicode), 56 bytes
(,⊖⍣(?2)↑a(3+⍳3)(10-⌽a←3?3)){⍺ ⍺⌷9 9⍴∊⌽⍵∘.⌽⍵⊖¨⊂3 3⍴⍳9}⍳3

Try it online!
A full program that randomly gives a 9-by-9 matrix of digits.
By OP mentioning "it must be possible to obtain at least 9 structurally different boards", I believe it was to prevent using just trivial transformations like reflection and rotation. But there are more possible transformations than that. I use two kinds of transformations:

Permute R19C19, R28C28 and R37C37 (6 cases)

Example: Swap R19C19 and R28C28

a b c - - - A B C     e d f - - - D F E
d e f - - - D E F     b a c - - - A C B
g h j - - - G H J     h g j - - - G J H
- - - - - - - - -     - - - - - - - - -
- - - - - - - - - ==> - - - - - - - - -
- - - - - - - - -     - - - - - - - - -
k l m - - - K L M     l k m - - - K M L
n p q - - - N P Q     s r t - - - R T S
r s t - - - R S T     p n q - - - N Q P

Reverse the order of boxes in both dimensions (2 cases: reverse both or keep intact)

a b c - - - A B C     K L M - - - k l m
d e f - - - D E F     N P Q - - - n p q
g h j - - - G H J     R S T - - - r s t
- - - - - - - - -     - - - - - - - - -
- - - - - - - - - ==> - - - - - - - - -
- - - - - - - - -     - - - - - - - - -
k l m - - - K L M     A B C - - - a b c
n p q - - - N P Q     D E F - - - d e f
r s t - - - R S T     G H J - - - g h j

resulting in 12 structurally different boards. Note that, in both cases, the thing that changes on the diagonals is the order of the digits. Also, the center box is always intact, so no two boards are equivalent under transliteration.
Part 1: Construct a valid diagonal sudoku board
⍝ A 3x3 box of 1..9
⊂3 3⍴⍳9
┌─────┐
│1 2 3│
│4 5 6│
│7 8 9│
└─────┘

⍝ The box rotated upwards 1, 2, 3 times
(⍳3)⊖¨⊂3 3⍴⍳9
┌─────┬─────┬─────┐
│4 5 6│7 8 9│1 2 3│
│7 8 9│1 2 3│4 5 6│
│1 2 3│4 5 6│7 8 9│
└─────┴─────┴─────┘

⍝ The boxes rotated left 1, 2, 3 times
(⍳3)∘.⌽(⍳3)⊖¨⊂3 3⍴⍳9
┌─────┬─────┬─────┐
│5 6 4│8 9 7│2 3 1│
│8 9 7│2 3 1│5 6 4│
│2 3 1│5 6 4│8 9 7│
├─────┼─────┼─────┤
│6 4 5│9 7 8│3 1 2│
│9 7 8│3 1 2│6 4 5│
│3 1 2│6 4 5│9 7 8│
├─────┼─────┼─────┤
│4 5 6│7 8 9│1 2 3│
│7 8 9│1 2 3│4 5 6│
│1 2 3│4 5 6│7 8 9│
└─────┴─────┴─────┘

⍝ Horizontally reverse the boxes, keeping the contents inside the boxes
⌽(⍳3)∘.⌽(⍳3)⊖¨⊂3 3⍴⍳9
┌─────┬─────┬─────┐
│2 3 1│8 9 7│5 6 4│
│5 6 4│2 3 1│8 9 7│
│8 9 7│5 6 4│2 3 1│
├─────┼─────┼─────┤
│3 1 2│9 7 8│6 4 5│
│6 4 5│3 1 2│9 7 8│
│9 7 8│6 4 5│3 1 2│
├─────┼─────┼─────┤
│1 2 3│7 8 9│4 5 6│
│4 5 6│1 2 3│7 8 9│
│7 8 9│4 5 6│1 2 3│
└─────┴─────┴─────┘

⍝ Enlist the digits and reshape into 9x9 matrix
⍝ (Each box goes to each row)
9 9⍴∊⌽(⍳3)∘.⌽(⍳3)⊖¨⊂3 3⍴⍳9
2 3 1 5 6 4 8 9 7
8 9 7 2 3 1 5 6 4
5 6 4 8 9 7 2 3 1
3 1 2 6 4 5 9 7 8
9 7 8 3 1 2 6 4 5
6 4 5 9 7 8 3 1 2
1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3

Part 2: Generate permutation vector
,⊖⍣(?2)↑a(3+⍳3)(10-⌽a←3?3)
                    a←3?3   ⍝ Generate a permutation of 1 2 3
                            ⍝ ex) 2 3 1
        a(3+⍳3)(10-⌽a    )  ⍝ Permutation vector in chunks of 3
                            ⍝ ex) (2 3 1)(4 5 6)(9 7 8)
       ↑                    ⍝ Promote to matrix
 ⊖⍣(?2)                     ⍝ Reverse vertically 1 or 2 times
                            ⍝ ex) [9 7 8][4 5 6][2 3 1]
,                           ⍝ Flatten ex) 9 7 8 4 5 6 2 3 1

Part 3: Permute the rows and columns
⍝ Permute both rows and columns of the matrix through indexing function
perm perm⌷mat
⍝ Using the example permutation above, the sudoku board is:
3 1 2 7 8 9 5 6 4
9 7 8 4 5 6 2 3 1
6 4 5 1 2 3 8 9 7
8 9 7 6 4 5 1 2 3
5 6 4 3 1 2 7 8 9
2 3 1 9 7 8 4 5 6
4 5 6 2 3 1 9 7 8
1 2 3 8 9 7 6 4 5
7 8 9 5 6 4 3 1 2


text:
The last stage of contamination
There is a virus inside a recipient of 5x5. As we know how it propagates its contamination, your mission is to output the last stage of the contamination.
The recipient
It will be representend as a two dimensional array of 5x5:
0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1

Where 1 means a position where the virus has already contaminated, and 0 a position not contaminated.
How the virus propagates

A contaminated position can not be clean.
A clean position will be contaminated in the next stage only if at least two of its adjacent positions (north, east, south and west cells) are contaminated.
The last stage of the contamination occurs when no more clean cells can be contaminated.

Sample
Using as as stage 1 of the contamination the recipient described above, the stage 2 will be:
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1

The stage 3 of the contamination will be:
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

The stage 4 of the contamination will be:
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

And the stage 5 (in this example, the last one) will be:
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

Challenge
Given as input one stage of the contamination, you should output the last stage of the contamination.
You are allowed to write full program or a function. You can take the input as array/list, as separated numbers, or even as string. Chooses the best way that fits to your language.
The shortest answer in bytes wins!
Another test cases
Input:
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0
1 0 0 0 1

Output:
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1

Input:
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Input:
1 0 0 1 0
0 0 1 0 1
0 0 0 0 0
1 0 0 0 0
0 0 1 0 0

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Input:
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0

Output:
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0

How can 1 0 1 occur in the output? Isn’t the center zero adjacent to two 1s?

@Lynn.. I've updated ;) ... sorry for that

Could you add 1 0 0 1 0 \ 0 0 1 0 1 \ 0 0 0 0 0 \ 1 0 0 0 0 \ 0 0 1 0 0 as a test case?

@CᴏɴᴏʀO'Bʀɪᴇɴ. Added thanks

All the test cases so far have only full row and columns finishing empty. I'd suggest 0 1 0 0 0 \ 0 0 0 0 1 \ 0 0 1 0 0 \ 1 0 0 0 0 \ 0 0 0 1 0, which stays unchanged.

@xnor. Sorry for the delay, and thanks for the test case, I've added :)

Since this is basically talking about a cellular automaton I give you..
Golly Quicklife rule, 10 bytes
01234/234V

Input the rule, paste the grid into Golly, run pattern. The resulting pattern is the output.
Explanation:
01234 Survive on any number of neighbors
     /234 Born on >2 neighbors
         V Only directly adjacent neighbors count

Or if you insist on a full RuleLoader rule, 89 bytes:
@RULE X
@TABLE
n_states:2
neighborhood:vonNeumann
symmetries:permute
011001
011101
011111

Rulename is X, same steps as before.

Is this a programming language?

Golly Quicklife can simulate B3/S23 which can do anything! ...But it does have strict input format (like the entire program is included in the input (how else would you do it?)). BUT WHY RUIN THE FUN??

Well, we just need to wait for a question that boils down to the long-term behavior of a cellular automaton!

I have some doubts about the validity. If Golly only displayed the final result, it would be fine, but it also displays intermediate results (unless I'm wrong)

It won't (Assuming you're on Golly 2.7 or earlier, OSX10.11) (but it's a bug) And plus WHY RUIN THE FUN??

@CatsAreFluffy You have my upvote then.

Slightly better answer to above question: Turn the speed up.

Python 2, 97 bytes
s=' '*6+input()
exec"s=s[1:]+('1'+s)[sum(s[i]<'1'for i in[-6,-1,1,6])>2or'/'>s];"*980
print s[6:]

Try it online. Input is taken as a quoted string with each row delimited by newlines. The 980 is not optimal and can be replaced with a lower multiple of 35. Since it has no impact on the length of this program, I have left the determination of the lowest safe upper bound as an exercise for the reader.

Requires quotes around input and \n escaped newlines.

@CatsAreFluffy I believe the Ideone link already clarifies how the input is taken.

Input is taken as a quoted string with each row delimited by \n s.

Alright, I'll edit it to make it less ambiguous.

Javascript (ES6), 91 89 87 bytes
As a function which accepts input as an array of numbers or strings.
-2 bytes from Neil (combining assignment of y with string conversion)
-2 bytes (removing variable j)

f=x=>(y=x.map((z,i)=>~(i%5&&x[i-1])+~(i%5<4&x[i+1])+~x[i-5]+~x[i+5]<-5|z))+[]==x?y:f(y)

<textarea id="input" cols="10" rows="5">0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1</textarea>
<button id="submit">Run</button>

Save 2 bytes by writing (y=...)+''==x instead of (y=...),y+''==x.

MATL, 22 bytes
tn:"t5Bt!=~2X53$Y+1>Y|

This works in current version (15.0.0) of the language.
Try it online!
Input format is: 2D array with rows separated by semicolons. So the four test cases have the following inputs:
[0 0 0 0 1; 0 0 0 0 1; 0 0 0 1 1; 0 0 1 1 1; 0 1 1 1 1]

[1 1 0 0 1; 0 0 0 0 0; 0 1 0 0 1; 0 0 0 0 0; 1 0 0 0 1]

[1 0 0 0 0; 0 1 0 0 0; 0 0 1 0 0; 0 0 0 1 0; 0 0 0 0 1]

[1 0 0 1 0; 0 0 1 0 1; 0 0 0 0 0; 1 0 0 0 0; 0 0 1 0 0]

Explanation
This repeatedly performs a 2D convolution of the input array with the following mask, which defines which neighbours count as contaminating:
0 1 0
1 0 1
0 1 0

In order to obtain a result the same size as the original array, it is first padded with a frame of zeros and then only the "valid" part of the convolution is kept (i.e. that without edge effects).
A threshold of 2 is applied to the output of the convolution, and the result is element-wise ORed with the original input.
This must be done a sufficient number of times to ensure the final state has been reached. A simple criterion that fulfills this is: iterate as many times as the number of entries in the input array (that is, 25 times in the test cases).
t          % get input 2D array implicitly. Duplicate
n:"        % repeat as many times as elements in the input array
  t        %   duplicate array
  5B       %   number 5 in binary: row vector [1 0 1]
  t!       %   duplicate and transpose into column
  =~       %   compare for inequality with broadcast. Gives desired mask
  2X53$Y+  %   2D convolution. Output has same size as input
  1>       %   true for elements equal or greater than 2
  Y|       %   element-wise OR with previous copy of the array
           % end loop. Implicitly display

TI-BASIC, 151 bytes
Prompt [A]
[A]→[B]
Lbl 0
[B]→[A]
For(Y,1,5
For(X,1,5
DelVar ADelVar BDelVar CDelVar D
If Y>1:[A](Y-1,X→A
If Y<5:[A](Y+1,X→B
If X>1:[A](Y,X-1→C
If X<5:[A](Y,X+1→D
max(A+B+C+D≥2,[A](Y,X→[B](Y,X
End
End
If [A]≠[B]:Goto 0
[B]

Input as [[1,0,0,1,1][1,0,0,0,0]...].

I think you can get this to about 100 bytes. First tip: Use a Repeat loop.

Lua, 236 bytes
s=arg[1]u=s.sub while p~=s do p=s s=s:gsub("(%d)()",function(d,p)t=0 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)t=t+(p-7>0 and u(s,p-7,p-7)or 0)t=t+(p+5<30 and u(s,p+5,p+5)or 0)t=t+(p%6>0 and u(s,p,p)or 0)return t>1 and 1 or d end)end print(s)

Accepts input on the command line, and uses Lua's string manipulation to get the answer.
Ungolfed:
s=arg[1]
u=s.sub
while p~=s do
    p=s
    s=s:gsub("(%d)()", function(d, p)
                 t=0
                 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)
                 t=t+(p-7>0 and u(s,p-7,p-7)or 0)
                 t=t+(p+5<30 and u(s,p+5,p+5)or 0)
                 t=t+(p%6>0 and u(s,p,p)or 0)
                 return t>1 and 1 or d
    end)
end
print(s)

APL, 76 72 70 bytes
{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡

What this does is: expand the matrix to a 7x7 one, then center our argument (omega). From this matrix, generate 4 "child" matrices, each one shifted in a different direction (up/down/left/right), add them together (so we get the number of neighbours), drop the frame (to go back to a 5x5 matrix). Or this new matrix with the "old" one, to make sure we didn't drop any cells in the process (i.e. at the edge).
Then, use the ⍣≡ combination to get to a fixed-point value.
{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡
                                                             7 7↑⍵    ⍝ Expand the matrix
                                                       ¯1⊖¯1⌽         ⍝ Center the original matrix
                  (1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂               ⍝ Construct 4 child matrices, each offset from the original one by the values on the left of {}
                +/                                                    ⍝ Sum each matrix into one giant matrix
               ↑                                                      ⍝ Mix
     ¯1 ¯1↓1 1↓                                                       ⍝ Transform the 7x7 matrix back to a 5x5 matrix
   1<                                                                 ⍝ Check which elements are smaller than 1
 ⍵∨                                                                   ⍝ "Or" this matrix and the generated matrix
{                                                                 }⍣≡ ⍝ Find the fixpoint

example (considering the function was assigned to contaminate):
          stage ⍝ the base matrix
0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
      contaminate stage ⍝ apply the function
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Parity of a Permutation
Background
The parity of a permutation, as defined by wikipedia, is as follows:

The sign or signature of a permutation σ is denoted sgn(σ) and defined as +1 if σ is even and −1 if σ is odd.
The sign of a permutation can be explicitly expressed as
sgn(σ) = (−1)^N(σ)
where N(σ) is the number of inversions in σ.
Alternatively, the sign of a permutation σ can be defined from its decomposition into the product of transpositions as
sgn(σ) = (−1)^m
where m is the number of transpositions in the decomposition.

For those of you who are not fond of Greek alphabet soup in their math, I'll try and simplify the definition a bit with an example (also stolen from wikipedia).
Example
Consider the input array {1, 2, 3, 4, 5}, and a permutation of it, let's say, {3, 4, 5, 2, 1}. In order to get from the original array to its permutation, you must swap indices 0 and 2, 1 and 3, then 2 and 4. Although this is not a unique solution, the parity is well-defined so this works for all cases.
Since it requires 3 swaps, we label this permutation with an odd parity. As you might expect, a permutation that requires an even amount of swaps is said to have an even parity.
Challenge
Your challenge is to write a program in as few bytes as possible to determine the parity of a permutation. Your program or function must:

Accept as arguments, two input arrays (or strings) representing a set before and after a permutation.
Return or print the character e for even or o for odd, given the permutation.
Should assume that all indices in the arrays or strings have unique values.

Test Cases
Assuming you declared a function named f:
f([10], [10]) == "e"
f([10, 30, 20], [30, 20, 10]) == "e"
f([10, 30, 20, 40], [30, 20, 40, 10]) == "o"

This is code-golf, the shortest program in bytes wins!

People won't like the strict output format. How about truthy for even and falsy for odd? (or the other way around)

I was actually hoping to retain the output format I specified unless anyone else really is bothered by it. Edit hold on, I'll compromise.

@CatsAreFluffy is that better?

Well, I guess we'll see!

Good night! Here are some suggestions for when you come back to this (but please do check yourself): [10], [10] -> e (zero transpositions). [10 30 20], [30 20 10] -> e (two transpositions). [10 30 20 40], [30 20 40 10] -> o (three transpositions)

The J language has a builtin C.!.2 for the sign of a permutation, giving a 15 character solution. It's not disallowed in the rules, but it's not really much fun either.

@DonMuesli I added the test cases you suggested.

Jelly, 13 12 bytes
żṗ2</€⁺Sị“oe

Try it online!
How it works
żṗ2</€⁺Sị“oe  Main link. Arguments: A, B (lists)

ż             Zip A with B. Yields an array of pairs [x, σ(x)].
 ṗ2           Generate all pairs [[x, σ(x)], [y, σ(y)]].
   </€        Reduce each pair by </€.
              This maps [[x, σ(x)], [y, σ(y)]] to [x < y, σ(x) < σ(y)].
      ⁺       Repeat the previous link, i.e., execute </€ once more.
              This maps [x < y, σ(x) < σ(y)] to ((x < y) < (σ(x) < σ(y))), which is
              true if and only if x > y and σ(x) < σ(y).
       S      Sum. This counts the number of inversions.
        ị“oe  Retrieve the letter at the corresponding index.
              Indexing is 1-based and modular, so an odd sum retrieves the first
              letter, an even sum the second.

That is impressively small. Kudos!

MATL, 17 16 bytes
1 byte removed thanks to a suggestion by Dennis
2$St!<Rz2\'oe'w)

This works in current version (15.0.0) of the language.
Try it online!
Explanation
This uses the definition of parity in terms of inversions. An inversion is a pair of elements in the second array that are in the "wrong" order compared with the first array. Since the first array need not be sorted, we first sort it and the same rearrangement needed for that sorting is applied to the second array. Then an inversion corresponds to a pair of elements that is not increasing in the second array.
Note also that the two input arrays can be swapped and the result is the same. So it's not important which array is considered to be the "original" and which the "permuted".
2$S     % implicitly take two row vectors. Sort second and apply the indices
        % of that sorting to the first
t!      % duplicate. Transpose into column vector
<       % true for elements of the column vector that exceed those of the
        % row vector. Gives a 2D array with all pairs of comparisons
R       % keep only upper triangular part of that array
z       % number of nonzero elements. This is the number of inversions
2\      % parity of that number: gives 0 or 1
'oe'w   % push string 'eo' below the top of the stack
)       % apply index to produce 'e' or 'o'. An index 1 refers to the first
        % element, whereas 0 refers to the last. Implicitly display

This is a really clever solution!

@AlexA. Thanks! I've edited the answer to clarify what the pre-ordering part does: we sort one array and then the same rearrangement needed for that sorting is applied to the other array.

You should add modular indexing to MATL. That would save 3 bytes here.

@Dennis Yes, I've often thought about that... but currently it uses a format where negative values have a different meaning. I chose that in order to have indices of the form x(1:end-2) etc without explicitly indicating the size of x. Not sure if it was a good choice, but I guess it's too late to change now :-) Maybe I'll find a compatible way to add modular indexing

...and indices exceeding current length are used to assign new values. But index 0 does have the meaning of "last entry", so I can save a byte (remove the increment). Thanks for the idea!

As of version 15.1.0, MATL includes modular indexing with scalar indices

As of version 17.0.0, modular indexing can be applied to non-scalar indices too

Haskell, 58 bytes
k%l|m<-zip k l=cycle"eo"!!sum[1|(a,b)<-m,(c,d)<-m,a<c,b>d]

Usage:
*Main> [8,3,5]%[5,3,8]
'o'

Same method as my Python answer. proud haskeller saved a byte with cycle.
Alternative from Wheat Wizard for 58 bytes (56 by modern convention of removing f=):
g m=cycle"eo"!!sum[0|(a,b)<-m,(c,d)<-m,a<c,b>d]
f=(g.).zip

You can write cycle"eo"!!... Instead of "eo"!!mod(...)2, saving one byte.

You can write this as g m=cycle"eo"!!sum[0|(a,b)<-m,(c,d)<-m,a<c,b>d];f=(g.).zip,  I don't know if this would have counted as a 2 byte saving at the time, but it does now.

Octave, 56 52 bytes
It seems nobody is using this approach so far: Basically I'm just using the determinants of the corresponding permutation matrices. The expression det(eye(nnz(a))(a,:)) returns the determinant of the permutation matrix defined by the vector a. Then it is just a matter of extracting the right character from the string, depending on the result.
p=@(v)eye(nnz(v))(v,:);@(a,b)'ole'(det(p(a)*p(b))+2)

Good idea to use the determinants. Ole!

Python 2, 68 bytes
lambda*M:"eo"[sum(a<b<M>A>B for a,A in zip(*M)for b,B in zip(*M))%2]

Usage:
>>> f=lambda*M:"eo"[sum(a<b<M>A>B for a,A in zip(*M)for b,B in zip(*M))%2]
>>> f([8,3,5],[5,3,8])
'o'

Counts the number of inversion pairs of two zipped lists, i,e. values (a,A) and (b,B) from each list at the same index with a<b and A>B. These comparisons are combines as a<b<M>A>B, using the property that the list M is greater than any number. The sum is then taken modulo 2 and turned into e or o.

JavaScript (ES6), 73 bytes
(a,b)=>"eo"[r=0,g=a=>a.map((e,i)=>a.slice(i).map(d=>r^=d<e)),g(a),g(b),r]

Since we're only interested in the parity, any duplicate transpositions simply cancel out. Conveniently JavaScript's array subscripts are not multidimensional.

Interesting place for a comma.. didn't know you could do that. Don't forget about currying for -1 byte

Mathematica, 31 bytes
If[Tr[Signature/@{##}]==0,o,e]&

Signature[list]
  gives the signature of the permutation needed to place the elements of list in canonical order

We can reorder one list to the other, by first reordering one list to any order (in this case the canonical order) and reorder this list to the final list. The sign of the overall permutation is even, iff the signs of the two sub-permutations are equal.

Mathematica, 77 bytes
If[Mod[Plus@@Length/@(Join[{0},#]&)/@PermutationCycles[#][[1]],2]==0,"e","o"]&

I agree!

Handy function, unfortunately long name!

Annoying, right? I hate Cycles. It bumps up the size of PermutationCycles's name, and even PermutationCycles is stupid, returning a Cycles object! `

05AB1E, 13 bytes
øDδ›Æ0›˜O„eoè

Try it online or verify all test cases.
Or alternatively:
øãε`›`›}O„eoè

Try it online or verify all test cases.
Both ports of @Dennis' Jelly answer, so make sure to upvote him as well!
Explanation:
ø             # Zip to pair the values in the two (implicit) input-lists together
 D            # Duplicate this list of pairs
  δ           # Apply double-vectorized with the two lists:
   ›          #  > check
              #   (e.g. [a,b] and [c,d] → [a>c,b>d]
    Æ         # Reduce each inner-most pair by subtracting: [a>c,b>d] → (a>c)-(b>d)
     0›       # Check if it's positive: (a>c)-(b>d)>0
       O      # Sum these checks together
           è  # Modular 0-based index it into
        „eo   # string "eo"
              # (which is output implicitly as result)

ø             # Same as above
 ã            # Cartesian product with itself to create pairs of pairs
  ε           # Map over each pair of pairs:
   `          #  Pop and push both pairs to the stack
    ›         #  [a,b] and [c,d] → [a>c,b>d]
     `        #  Pop these values to the check again
      ›       #  (a>c) and (b>d) → (a>c)>(b>d)
  }           # Close the map
   O„eoè      # Same as above, including implicit output

Minor note: Jelly uses 1-based indexing and 05AB1E uses 0-based, which is why his string is "oe" and mine is "eo".

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
A curious prime fraction formula
Given a positive integer \$n\$ output the integers \$a\$ and \$b\$ (forming reduced fraction \$a/b\$) such that:
$$\frac a b = \prod ^n _{k=1} \frac {p^2_k - 1} {p^2_k + 1}$$
Where \$p_k\$ is the \$k\$ th prime number (with \$p_1 = 2\$).
Examples:
1   -> 3, 5
2   -> 12, 25
3   -> 144, 325
4   -> 3456, 8125
5   -> 41472, 99125
15  -> 4506715396450638759507001344, 11179755611058498955501765625
420 -> very long
Probabilistic prime checks are allowed, and it's ok if your answer fails due to limitations in your language's integer type.

Shortest code in bytes wins.

Can we also output 3.0 instead of 3?

@AandN I guess... Make sure your program is correct for all inputs though, and does not suffer from floating point errors for big inputs.

Can we output a and b as a rational type?

@AlexA. Only if the output clearly shows both integers.

@Dennis For this challenge I'll be lenient (poke around in chat history for discussion around this) and remove restrictions.

"it's ok if your answer fails due to limitations in your language's integer type" TODO: write a language with a 1 bit integer type...

@SamYonnou Those already exist, but abusing native number types to trivialize a problem is one of the loopholes that are forbidden by default.

It wasn't mentioned in the original post, but a/b converges on 2/5. More info here: http://mathoverflow.net/questions/164092/computing-prod-p-fracp2-1p21-without-the-zeta-function.

M, 9 bytes
RÆN²‘İḤCP

Try it online!
Trivia
Meet M!
M is a fork of Jelly, aimed at mathematical challenges. The core difference between Jelly and M is that M uses infinite precision for all internal calculations, representing results symbolically. Once M is more mature, Jelly will gradually become more multi-purpose and less math-oriented.
M is very much work in progress (full of bugs, and not really that different from Jelly right now), but it works like a charm for this challenge and I just couldn't resist.
How it works
RÆN²‘İḤCP  Main link. Argument: n

R          Range; yield [1, ..., n].
 ÆN        Compute the kth primes for each k in that range.
   ²‘      Square and increment each prime p.
     İ     Invert; turn p² + 1 into the fraction 1 / (p² + 1).
      Ḥ    Double; yield 2 / (p² + 1).
       C   Complement; yield 1 - 2 / (p² + 1).
        P  Product; multiply all generated differences.

Is ÆN the only M-specific operator? Also Melly

None of these operators are specific to M. The difference is that M calculates a fraction, while Jelly calculates a floating point number.

Mathematica, 32 bytes
1##&@@(1-2/(Prime@Range@#^2+1))&

An unnamed function that takes integer input and returns the actual fraction.
This uses the fact that (p2-1)/(p2+1) = 1-2/(p2+1). The code is then golfed thanks to the fact that Mathematica threads all basic arithmetic over lists. So we first create a list {1, 2, ..., n}, then retrieve all those primes and plug that list into the above expression. This gives us a list of all the factors. Finally, we multiply everything together by applying Times to the list, which can be golfed to 1##&.
Alternatively, we can use Array for the same byte count:
1##&@@(1-2/(Prime~Array~#^2+1))&

1-2=1, right?

@CatsAreFluffy Yeah (-1 actually), but 1-2/x ≠ -1/x. ;)

@Range@±~Array~

31 bytes

Python 2, 106 bytes
from fractions import*
n=input()
F=k=P=1
while n:b=P%k>0;n-=b;F*=1-Fraction(2*b,k*k+1);P*=k*k;k+=1
print F

The first and fourth lines hurt so much... it just turned out that using Fraction was better than multiplying separately and using gcd, even in Python 3.5+ where gcd resides in math.
Prime generation adapted from @xnor's answer here, which uses Wilson's theorem.

Ruby, 122 77 65 bytes
Thanks to Sherlock for shaving off 10 bytes.
require'prime'
->n{Prime.take(n).map{|x|1-2r/(x*x+1)}.reduce(:*)}

Defines an anonymous function that takes a number and returns a Rational.

Pyth, 26 25
/RiFN=N*MCm,tdhd^R2.fP_ZQ

Try it here or run the Test Suite.
1 byte saved thanks to Jakube!
Pretty naive implementation of the specifications. Uses the spiffy "new" (I have no idea when this was added, but I've never seen it before) P<neg> which returns whether the positive value of a negative number is prime or not. Some of the mapping, etc can probably be golfed...

PARI/GP, 33 bytes
n->prod(i=1,n,1-2/(prime(i)^2+1))

Alternate version (46 bytes):
n->t=1;forprime(p=2,prime(n),t*=1-2/(p^2+1));t

Non-competing version giving the floating-point (t_REAL) result (38 bytes):
n->prodeuler(p=2,prime(n),1-2/(p^2+1))

Jelly, 14 13 bytes
RÆN²µ’ż‘Pµ÷g/

Try it online! Thanks to @Dennis for -1 byte.
R                       Range [1..n]
 ÆN                     Nth prime
   ²                    Square
    µ                   Start new monadic chain
     ’ż‘                Turn each p^2 into [p^2-1, p^2+1]
        P               Product
         µ              Start new monadic chain
          ÷             Divide by...
           g/           Reduce GCD

Julia, 59 42 bytes
n->prod(1-big(2).//-~primes(2n^2)[1:n].^2)

This is an anonymous function that accepts an integer and returns a Rational with BigInt numerator and denominator.
We begin by generating the list of prime numbers less than 2n2 and selecting the first n elements. This works because the nth prime is always less than n2 for all n > 1. (See here.)
For each p of the n primes selected, we square p using elementwise power (.^2), and construct the rational 2 / (p + 1), where 2 is first converted to a BigInt to ensure sufficient precision. We subtract this from 1, take the product of the resulting array of rationals, and return the resulting rational.
Example usage:
julia> f = n->prod(1-big(2).//-~primes(2n^2)[1:n].^2)
(anonymous function)

julia> f(15)
4506715396450638759507001344//11179755611058498955501765625

Saved 17 thanks to Sp3000!

Convex, 28 bytes
Convex is a new language that I am developing that is heavily based on CJam and Golfscript. The interpreter and IDE can be found here. Input is an integer into the command line arguments. Indexes are one-based. Uses the CP-1252 encoding.
,:)_{µ²1-}%×\{µ²1+}%×¶_:Ðf/p

You may or may not consider this answer to be competing since I was working on a few features that this program uses before the challenge was posted, but the commit was made once I saw this challenge go out.

MATL, 18 bytes
:Yq2^tqpwQpZd1Mhw/

Try it online!
Fails for large inputs because only integers up to 2^52 can be accurately represented internally.
Explanation
:     % implicitly take input n. Generate range [1,...,n]
Yq    % first n prime numbers
2^    % square
tqp   % duplicate. Subtract 1. Product
wQp   % swap. Add 1. Product
Zd    % gcd of both products
1M    % push the two products again
h     % concatenate horizontally
w/    % swap. Divide by previously computed gcd. Implicitly display

Mathematica, 45 bytes
Times@@Array[(Prime@#^2-1)/(Prime@#^2+1)&,#]&

Primes? Fractions? Mathematica.

Haskell, 53 bytes
Anonymous function, 53 characters:
(scanl(*)1[1-2%(p*p+1)|p<-nubBy(((>1).).gcd)[2..]]!!)

Try it here (note: in standard GHCi you need first to make sure Data.Ratio and Data.List are imported):
λ (scanl(*)1[1-2%(p*p+1)|p<-nubBy(((>1).).gcd)[2..]]!!) 5
41472 % 99125
:: Integral a => Ratio a

Haskell's list indexing !! is 0-based. (___!!) is an operator section, forming an anonymous function so that (xs !!) n == xs !! n.
It's four bytes less to generate the whole sequence:
λ mapM_ print $ take 10 $     -- just for a nicer output
    scanl(*)1[1-2%(n*n+1)|n<-[2..],all((>0).rem n)[2..n-1]]
1 % 1
3 % 5
12 % 25
144 % 325
3456 % 8125
41472 % 99125
3483648 % 8425625
501645312 % 1221715625
18059231232 % 44226105625
4767637045248 % 11719917990625
:: IO ()

Japt v2.0a0, 25 bytes
_j}jU £[X²ÉX²Ä]ÃyÈ×ÃË÷Fry

Try it

Vyxal, 11 bytes
ʁǎ²₍‹›vΠ:ġḭ  # main program

ʁ            # range 0 to input
 ǎ²          # ith prime, sqaured
   ₍‹›       # push the increment and decrement of that list wrapped
      vΠ     # take the product of both lists
        :ġ   # duplicate, get the gcd
          ḭ  # divide both numbers by the gcd, print implicitly

I don't think the strategy of 1-2/p^2-1 works in Vyxal because it would just end with a floating point number rather than a fraction, but feel free to prove me wrong. (If it did work, it would be a literal translation from Dennis' M answer, but with a byte shaved off for the nth primes, coming out to 8)
Try it Online!

Seriously, 25 bytes
,r`PªD;⌐k`M┬`π`Mi│g;)@\)\

Outputs a\nb (\n is a newline). Large inputs will take a long time (and might fail due to running out of memory) because prime generation is pretty slow.
Try it online!
Explanation:
,r`PªD;⌐k`M┬`π`Mi│g;)@\)\
,r                         push range(input)
  `PªD;⌐k`M                map:
   P                         k'th prime
    ª                        square
     D                       decrement
      ;                      dupe
       ⌐                     add 2 (results in P_k + 1)
        k                    push to list
           ┬               transpose
            `π`M           map product
                i│         flatten, duplicate stack
                  g;)      push two copies of gcd, move one to bottom of stack
                     @\    reduce denominator
                       )\  reduce numerator

The title looks hilarious. I read it as "Seriously, 25 bytes ?! "

@AlexKChen It's been nearly 2 years since I created the language, and it's just now paid off :)

Husk, 11 bytes
Πmo§/→←□↑İp

Try it online!

J, 18 bytes
[:*/1-2%1+*:@p:@i.

Try it online!
Uses the same formula that Martin Ender's answer does.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Score a game of Load, Defend and Shoot
When I was a child, I used to play this game a lot.
Rules
There are two players (let's call them A and B), and each player uses his hands as guns. There are three possible moves:

Hands up to load ammunition to your gun.
Each gun starts empty. Loading increases the ammunition by one.
Hands pointing to the other player to shoot.
This decreases the ammunition by one. You must have at least one unit of ammo to shoot.
Crossed arms to protect yourself from a shot.

Both players move simultaneously. If both players shoot at the same time, the bullets hit each other, and the game continues. The game ends when one player shoots while the other is loading ammunition.
Shooting and empty gun is considered cheating. If a player cheats while the other one performs a legal action, the cheater loses immediately. If both players cheat at the same time, the game continues.
Cheating attempts do not decrease ammunition, so it can never be negative.
Challenge
Given the moves made by players A and B, output which player won the game: 1 for player A, -1 for player B, and 0 for a draw. You can use any other triple of return values, but you need to state in your answer which ones you use.
The game may:

end without having to process all moves;
not end with the given moves, and thus it is considered a draw.

The input can be taken:

as strings
as arrays/lists of integers
in any other way that does not pre-process the input

Full program or functions allowed. Since this is code-golf, the shortest answer in bytes wins!
Test cases
A: "123331123"
B: "131122332"
    -----^                Player B shoots player A and wins.

Output: -1

A: "111322213312"
B: "131332221133"
    -------^              Player B cheats and loses.

Output: 1

A: "1333211232221"
B: "1213211322221"
    ----------^^          Both players cheat at the same time. The game continues.

Output: 0

A: "12333213112222212"
B: "13122213312232211"
         |       || ^---- Player A shoots player B and wins.
         ^-------^^------ Both players cheat at the same time. The game continues.

Output: 1

Related KotH (interestingly, I've never played this variant of the game; I think the linked question was inspired by a friend who had, but it was long enough ago that I don't remember anymore).

Jelly, 33 32 24 bytes
Zæ%1.»0$+¥\>-‘żZḅ3Ff5,7Ḣ

This prints 5 instead of -1, and 7 instead of 1. Try it online! or verify all test cases.
How it works
Zæ%1.»0$+¥\>-‘żZḅ3Ff5,7Ḣ  Main link. Argument: A (digit list array)

Z                         Zip; group corresponding digits.
 æ%1.                     Map the digits in (-1.5, 1.5].
                          This replaces [1, 2, 3] with [1, -1, 0].
          \               Cumulatively reduce the pairs by doing the following.
     »0$                    Take the maximum of the left value and 0, i.e., replace
                            a -1 with a 0.
        +¥                  Add the modified left value to the right value.
                          This computes the available ammo after each action. An
                          ammo of -1 indicates a cheating attempt.
           >-             Compare the results with -1.
             ‘            Increment. And unilateral cheating attempt is now [1, 2]
                          or [2, 1], where 1 signals the cheater and 2 the winner.
              żZ          Pair each result with the corr., original digits.
                ḅ3        Convert each pair from base 3 to integer.
                          This maps [1, 2] and [2, 1] to 5 and 7.
                  F       Flatten the resulting, nested list.
                   f5,7   Discard all but 5's and 7's.
                       Ḣ  Grab the first element (5 or 7).
                          If the list is empty, this returns 0.

Pyth, 48 46 49 47 bytes
.xhfT|M.e,-FmgF.b/<dhkY2S2Q?}b_BS2-FbZ.b,NYCQ)0

Try it here!
Thanks to @isaacg for saving 2 4 bytes!
Takes input as a 2-tuple with the list of the moves of player A first and the moves of player B second. Output is the same as in the challenge.
Explanation
Short overview

First we group the moves of both players together, so we get a list of 2-tuples.
Then we map each of those tuples to another 2-tuple in the form [cheating win, fair win] with the possible values -1, 0, 1 for each of it, to indicate if a player won at this point (-1, 1) or if the game goes on (0)
Now we just need to get the first tuple which is not [0,0], and take the first non-zero element of it which indicates the winner

Code breakdown

.xhfT|M.e,-FmgF.b/<dhkY2S2Q?}b_BS2-FbZ.b,NYCQ)0  # Q = list of the move lists

                                      .b,NYCQ    # pair the elements of both input lists
       .e                                        # map over the list of pairs with
                                                 # b being the pair and k it's index
            m             Q                      # map each move list d
               .b      2S2                       # map over [1,2], I can't use m because it's
                                                 # lambda variable conflicts with the one from .e
                  <dhk                           # d[:k+1]
                 /    Y                          # count occurences of 1 or 2 in this list
          -F                                     # (count of 1s)-(count of 2s), indicates cheating win
                           ?}b_BS2               # if b is (1,2) or (2,1)
                                  -Fb            # take the difference, indicates fair win
                                     Z           # else 0, no winner yet
         ,                                       # pair those 2 values
     |M                                          # For each resulting pair, take the first one if
                                                 # its not zero, otherwise the second one
   fT                                            # filter all zero values out
.xh                                              # try to take the first value which indicates the winner
                                             )0  # if thats not possible because the list is empty
                                                 # output  zero to indicate a draw

m|Fd is the same as |M.

@isaacg Thanks! I always forget that M does splatting as well. Btw: The issue about conflicting lambda variables we discussed in chat is costing me several bytes here :P

,1 2 is the same as S2

I've added another testcase ;)

@isaacg Thanks again! Don't know how I missed that.

Java, 226 212 200 196 194 bytes
-14 bytes by re-ordering logic
-12 bytes thanks to Mr Public pointing out how to use a ternary operation for the shooting logic
-4 bytes by cramming load logic into one short-circuiting if
-2 bytes because ==1 === <2 when input can only be 1,2,3
(a,b)->{for(int m=0,n=0,w,v,r=0,i=0,x;i<a.length;){w=a[i];v=b[i++];x=w==2?m<1?r--:m--:0;x=v==2?n<1?r++:n--:0;if(r!=0)return r;if(w<2&&++m>0&v==2)return -1;if(v<2&&++n>0&w==2)return 1;}return 0;}

Usage and indented version:
static BiFunction<Integer[], Integer[], Integer> game = (a,b) -> {
    for(int m=0,n=0,w,v,r=0,i=0,x;i<a.length;) {
        w=a[i];v=b[i++];
        // shoot
        x=w==2?m<1?r--:m--:0;
        x=v==2?n<1?r++:n--:0;
        if(r!=0)return r;
        // load
        if(w<2&&++m>0&v==2)return -1;
        if(v<2&&++n>0&w==2)return 1;
    }
    return 0;
};

public static void main(String[] args) {
    System.out.println(game.apply(new Integer[] {1,2,3,3,3,1,1,2,3}, new Integer[] {1,3,1,1,2,2,3,3,2}));
    System.out.println(game.apply(new Integer[] {1,1,1,3,2,2,2,1,3,3,1,2}, new Integer[] {1,3,1,3,3,2,2,2,1,1,3,3}));
    System.out.println(game.apply(new Integer[] {1,3,3,3,2,1,1,2,3,2,2,2,1}, new Integer[] {1,2,1,3,2,1,1,3,2,2,2,2,1}));
}

Not so straightforward implementation of the game rules anymore, but simple. Each cycle, does these operations:

Load moves into temp variables
If player shot

without ammo: bias cheater towards losing
with ammo: decrement ammo

If cheater is not 0, return the value because someone cheated
If player reloaded

increment ammo
if other player shot, return loss

x is a dummy variable used to make the compiler let me use a ternary expression.
Wait, Java is SHORTER than Python?

I've added another testcase ;)

@WashingtonGuedes And mine works on this case thanks to my logic reordering!

Can the ifs be made into ternarys? e.g. w==2&&m<1?r--:m++

@Downgoat the else goes with the inner if so as you've written it the tertiary wouldn't work. However, I can probably do so with the inner if. I'll test it when I get a chance.

oh, then would w==2?m<1&&r--:m++ work?

@CAD97 @Downgoat You can actually use ternary operators for the if-statements. For the first ternary, int x=w==2?m<1?r--:r:m--; then continue to use the x (as this is just a dummy variable to make the ternary operate) like x=v==2?n<1?r++:r:n--;

@MrPublic I had to change the order to get the logic to work, but thanks for pointing out how to convince the compiler to let us use a ternary!

Would m=n=r=i=0 work instead of putting 0 multiple times?

@Blue it works out to be 2 characters longer. Removing =0 in the initial declaration then adding m= for each variable leaves 0; to be added. (That was a bad explanation.)

@CAD97 ah, I forgot that Java doesn't particularly like the nested declarations (like the one I showed earlier).

Python, 217 bytes
def f(A,B):
 x=y=0;c=[-1,1,0]
 for i in range(len(A)):
  a=A[i];b=B[i]
  for s in[0,1]:
   if(a,b)==(2,1):return c[s]*c[x<1]
   if(a,b)==(2,3)and x<1:return-c[s]
   x-=c[a-1];x+=x<0;a,b,x,y=b,a,y,x
 return 0

Explanation: Takes A and B as lists of integers. Simply goes through each pair of moves, adds or subtracts 1 if needed and returns when someone cheats or wins. Does the same thing twice using another for loop, once for A's move and once for B's move. Adds 1 if x goes below 0 to -1.


text:
Music Interval Solver

In music theory, an interval is the difference between two pitches. Each pitch is defined by the number of half-steps (The difference between C and C#) or whole steps (The difference between C and D). One whole step is the same as two half-steps. Here is a list of all the default intervals and the number of half-steps they represent:
0     Perfect Unison
2     Major Second
4     Major Third
5     Perfect Fourth
7     Perfect Fifth
9     Major Sixth
11    Major Seventh
12    Perfect Octave

There are 3 variations on the default intervals, minor, diminished, and augmented.

A minor interval is one half-step lower than a major interval, but not a perfect interval. So you have a minor second (1), a minor third (3), a minor sixth (8), and a minor seventh (10). There is no such thing as a minor fourth, minor fifth, minor unison or minor octave since these are all perfect intervals.

A diminished interval is one half-step lower than a minor or perfect interval. There is diminished Second (0), diminished third (2), diminished fourth (4), diminished fifth (6), diminished sixth (7), diminished seventh (9) and diminished octave (11).

An augmented interval is one half-step higher than a major or perfect interval. We have Augmented Unison (1), Augmented Second (3), Augmented third (5), Augmented Fourth (6), Augmented fifth, (8), Augmented sixth (10), and Augmented seventh (12).

The challenge:
You must write a program or function that takes a number of half steps or whole steps and then prints one of the valid English descriptions of this interval. It doesn't matter which description you pick, as long as it exactly matches the IO table. You can take this as one string
"5w" == 5 whole steps
"3h" == 3 half steps

or as a number and a string/char.
5, "w" == 5 whole steps
3, "h" == 3 half steps.

You can assume that every input will be between 0 and 12 half steps.
IO table
Here is a full list mapping the number of half-steps to all acceptable outputs.
0       Perfect unison, Diminished second
1       Minor second, Augmented unison
2       Major second, Diminished third
3       Minor third, Augmented second
4       Major third, Diminished fourth
5       Perfect fourth, Augmented third
6       Diminished fifth, Augmented fourth
7       Perfect fifth, Diminished sixth
8       Minor sixth, Augmented fifth
9       Major sixth, Diminished seventh
10      Minor seventh, Augmented sixth
11      Major seventh, Diminished octave
12      Perfect octave, Augmented seventh

Here is some sample I/O:
5w      Minor Seventh
5h      Augmented Third
12h     Perfect Octave
12w     UNDEFINED
1w      Diminished third
2h      Major Second

Dimished?....

@CatsAreFluffy My poor spelling has dimished my ability to write good challenges. ಠ_ಠ

Still a good challenge, just with more edits! :P

Ruby, Rev B 138 bytes
->n,s{i=12-n-n*(s<=>?h)
[a='Augmented','Major','Minor',d='Diminished',a,'Perfect',d][i%7]+' '+%w{seventh fifth third unison}[i%7/4+i/7*2]}

5 bytes saved by not repeating Augmented/Diminished. 1 byte saved by use of ?h.
Ruby, Rev A 144 bytes
->n,s{i=12-n-n*(s<=>'h')
%w{Augmented Major Minor Diminished Augmented Perfect Diminished}[i%7]+' '+%w{seventh fifth third unison}[i%7/4+i/7*2]}

The idea is to minimise the number of basic intervals (seventh fifth third and unison only) and take advantage of the fact that sevenths and fifths have an analogous relationship to that between thirds and unisons.
There are four types of seventh/third and 3 types of fifth/unison so the index variable i is set to 12 minus the number of half steps, so that the first term of the expression i%7/4 + i/7*2 will correctly select the type of basic interval.
ungolfed in test program
f=->n,s{                 #n = number of steps. s= step size, w or h
  i=12-n-n*(s<=>'h')     # i=12-n. If s is later in the alphabet than 'h' subtract again for whole steps
  %w{Augmented Major Minor Diminished Augmented Perfect Diminished}[i%7]+
  ' '+%w{seventh fifth third unison}[i%7/4+i/7*2]
}

-1.upto(12){|j|
puts f[j,'h']
}

0.upto(6){|j|
puts f[j,'w']
}

output
Diminished unison
Perfect unison
Augmented unison
Diminished third
Minor third
Major third
Augmented third
Diminished fifth
Perfect fifth
Augmented fifth
Diminished seventh
Minor seventh
Major seventh
Augmented seventh

Perfect unison
Diminished third
Major third
Diminished fifth
Augmented fifth
Minor seventh
Augmented seventh

Undefined behaviour inputs: The function gives the correct answer of diminished union for -1 halfsteps, but fails for inputs over 12. For example, it outputs perfect unison for 14 half steps, as the algorithm is based on a cycle of 14 rather than 12.

Python 2.7, 155 bytes
s='second unison third fourth sixth fifth seventh octave Diminished Augmented'.split()
def f(n,c):x=0xDE9CB87561430>>[4,8][c>'h']*n;print s[x%2+8],s[x/2%8]

Python 2, 149 bytes
def f(n,c):n*=1+(c>'h');print(n-6)%13%2*"Diminished"or"Augmented",'octave seventh sixth fifth fourth third second unison'.split()[71056674174>>3*n&7]

First, whole steps are converted to half steps.
Then, Diminished vs Augmented is printed. These alternate for adjacent n except that n=5 and n=6 give the same, which is achieved by first putting them across a boundary modulo an odd number.
Finally, the distance is printed, computed via a three-bit lookup table. This is shorter than doing int('6746543230210'[n]).

Retina, 153 bytes
\d+
$*
(.*)w|h
$1$1
^1*$
$.0
^[02479]|11
Diminished $0
^\d
Augmented $0
10|7
sixth
11
octave
12|9
seventh
8
fifth
4|6
fourth
5|2
third
1
unison
\d
second
Input number is first converted to unary, then doubled if followed by w,  and any letters are removed, leaving only the unary number. This number is then converted back to decimal. Finally, some search and replace is applied to construct the final output.
Example runs:

6w => 111111w  => 111111111111 => 12 => Augmented 12 => Augmented seventh
7h => 1111111h => 1111111      => 7  => Diminished 7 => Diminished sixth
3w => 111w     => 111111       => 6  => Augmented 6  => Augmented fourth
0h => h        =>              => 0  => Diminished 0 => Diminished second
Try it online!

Vitsy, 166 bytes
Well, this can definitely be further golfed.
WW2M1+*a+mZ
'dehsinimiD'
'roniM'
'rojaM'
'tcefreP'
'detnemguA'
'dnoces '
'htruof '
'htxis '
'evatco '
6m1m
6m2m
6m3m
6m5m
7m1m
7m4m
7m5m
8m1m
8m2m
8m3m
8m5m
9m1m
9m4m

This works by defining the minimal amount of items possible, then calling those items through the method syntax.
Try it Online!

Java, 225 224 bytes
There has got to be a better way to pack these strings but I don't have any ideas.
(i,s)->{String A="Augmented",M="Major",m="Minor",P="Perfect",D="Diminished",d=" Second",f=" Fourth",a=" Sixth",C=" Octave";String[]o=new String[]{D+d,m+d,M+d,A+d,P+f,A+f,D+a,m+a,M+a,A+a,D+C,P+C};i*=s=='w'?2:1;return o[i-1];}

Indented:
static BiFunction<Integer, Character, String> interval = (i,s) -> {
    String A="Augmented",M="Major",m="Minor",P="Perfect",D="Diminished",
            d=" Second",f=" Fourth",a=" Sixth",C=" Octave";
    String[] o = new String[] {D+d,m+d,M+d,A+d,P+f,A+f,D+a,m+a,M+a,A+a,D+C,P+C};
    i *= s=='w' ? 2 : 1;
    return o[i-1];
};

I believe you can shorten it by replacing if(s=='w')i*=2; with i*=s=='w'?2:1;

@MrPublic You are correct.

Javascript 189 bytes
a=>(n='sutsftfxFvxov'[N=parseInt(a)*(a.slice(-1)>'v'?2:1)])&&((N>5?N+1:N)%2?'Augmented ':'Dimished ')+'unison,second,third,fourth,fifth,sixth,seventh,octave'.split`,`['ustfFxvo'.indexOf(n)]

 F=
  a=>
    (n='sutsftfxFvxov' //using the right side of the possible answers
                       //set n = the letter representing
                       //unison, first, second ...

       //set N to 12 for 12h, but 24 for 12w
       [N=parseInt(a)*(a.slice(-1)>'v'?2:1)])

  &&   //if we were out of range (12w) we'll return undefined

    (
      (N>5?N+1:N)%2?  //get Aug or Dim (right side goes)
                      //DADADAADADADA
                      //     ^^ makes this a pain
       'Augmented ':'Dimished '
     )
     +
            //turn n (which is u for unison, x for sixth, etc
            //into it's full name
       'unison,second,third,fourth,fifth,sixth,seventh,octave'
         .split`,`
     ['ustfFxvo'.indexOf(a)]


text:
Solve a Linear Equation
This challenge but with a better spec.
Spec
Your program will take a linear equation containing a single variable x and output the value of x.
Input / Parsing

The input will only contain numbers, operators, parenthesis (()), x, and an = sign (this means no whitespace).
Parenthesis will always be balanced.
There will always be at least 1 x. An x may be preceded by a number.
All equations will exactly have one result.

A number can be defined by following these steps. A number can be defined by the regex: -?(\d+(\.\d+)?|\.\d+).

If you don't speak regex: A digit is defined as 0-9

It may have a - at the beginning of it signifying negative
Then there may be some digits. If they aren't any digits there will be a decimal point
If a decimal point exists, at least one digit will follow it

The biggest a number / value will be is defined by your language's capabilities.

An operator is any of: +-*/, they will always appear between numbers, and or parenthesis
this means (5)(5) is not a valid input for the sake of simplicity.

Parenthesis will always contain a valid expression (a valid combination of numbers and/or operators) inside them. "Balanced" parenthesis is defined as every ( will have an associated closing )
Evaluation

Order of operations should be followed and the precedences are (highest to lowest):

Parenthesis (most deeply nested first)
Multiplication & Division
Addition & Subtraction

If two operators with the same precedence are occurred you should prefer going left -> right

Output
You should output the result in some way. If you don't output just number result, clarify in your answer how the output is outputted. Your output format should be consistent. Output may be a decimal, but it will always be rational, the precision is limited to your language's precision. Only if your language does not support floating point arithmetic, you do not need to support it.
Rules

Built-ins trivializing this task are allowed but, you must clearly add [uses built-in] clearly to the header of the answer. This exempts your answer from winning
A "Built-ins trivializing this task" is any of:

Something which takes in an equation and outputs the value for a/the variable
Something which will completely simplify an equation
Using eval or a related function to do a significant amount of the parsing.  Use of eval and related functions are disallowed if they are used to (with minimal modification to the input) solve linear equations.
If you're in doubt, just ask in a comment.

Built-ins which parse the equation are allowed

Examples
3+4=x
7

4+x=5
1

3+3*3=x
12

3x-4=7+2x
11

3--1=x
4

3*(2+4x)=7x-4
-2

1.2+2.3x=5.8
2

10=4x
2.5

INVALID Inputs:
(5)(4)=x  no operator between (5) and (4)
5(x+3)=2  no operator 5 and (...)
x=y       the only variable is x
4=3       there is no x
x+3=x-7   no solution
x=x       infinite solutions
+5=x      + is not an unary operator. -5=x would be valid though
1/(x-3)=5 Nonlinear
3/x       Nonlinear

You say that built-ins disqualify your submission, but clarify this to refer only to operations that do equation solving and parsing and the like. I think it would be clearer to use a different term, since I think of any named operation as a built-in.

How accurate do the answers have to be?

@MrPublic Your program will take a linear equation containing a single variable...

Also, does JavaScript's eval count as trivializing the challenge? Also, would forms of new Function(...) count?

@CᴏɴᴏʀO'Bʀɪᴇɴ depends what you use it for. But assuming you're using JavaScript I don't see how it will trivialize the challenge so sure

Can there be x*x-x*x+1=x? (also linear)

JavaScript ES6, 246 bytes
Still some golfing to be done, but at least it's a solution!
C=a=>new Function("x","return "+a.replace(/(\d)x/g,"$1*x"));n=>{n=n.split("=");t=Math.abs,r=C(n[0]),c=C(n[1]),a=0,i=r(a)-c(a);a++;v=r(a)-c(a);o=t(i)<t(v)?-1:1;for(u=1/0;r(a)!==c(a);)a+=o,e=t(r(a)-c(a)),e>u&&(u=1/0,o/=10),u=Math.min(e,u);return a}

Name the function n=>{n=n.split("=")... to use it.
Hyper-ungolfed:
function solveLinear(equation){
    equation = equation.split("=");
    var abs = Math.abs;
    var LHS = convertToFunction(equation[0]), RHS = convertToFunction(equation[1]);
    var pivot = 0;
    var dir;
    var dir1 = LHS(pivot) - RHS(pivot);
    pivot++;
    var dir2 = LHS(pivot) - RHS(pivot);
    if(abs(dir1)<abs(dir2)) dir = -1;
    else dir = 1;
    var dif, minDif = Infinity;
    while(LHS(pivot) !== RHS(pivot)){
        pivot += dir;
        dif = abs(LHS(pivot) - RHS(pivot));
        if(dif > minDif){
            minDif = Infinity;
            dir /= 10;
        }
        minDif = Math.min(dif, minDif);
        console.log(pivot,dir,dif,minDif);
    }
    return {
        x: pivot,
        LHS: LHS,
        RHS: RHS
    };
}

This uses a pivot approach. (I'm not sure if this is what the algorithm is called, just a name I invented.) It first gathers which direction to search for from zero (i.e., which way the slopes of the two sides of the equations will intersect) and looks for the value. Once it finds a point of minimal difference, it goes to that point and decreases the search increment. This eventually yields as precise of a solution we need.

I think you could shave a good bit by using eval+ES6 syntax instead of Function new

JavaScript (Node.js), 106 93 bytes
a=>eval(`f=x=>${a[R='replace'](/(\d)x/g,"$1*x")[R]("=","-(")[R](/-/g,"+-")})`)(0)/(f(0)-f(1))

Try it online!
-13 bytes thanks to @tsh
Ungolfed:
var h=a=>{
  a=a.replace(/(\d)x/g,"$1*x").replace("=","-(").replace("--","- -"); //get into an eval-able form
  var f=x=>eval(a+")");
  var df=(f(1)-f(0))/(1-0) //derivative or slope of the function
  var x=0;
  return x-(f(x)/df); //newton's method
}

Explaination:
This solution works by Newton's method for finding roots. The code subtracts the right hand side of the equation from the left hand side, such that when f(x)=0, x will equal the value we are solving for. Therefore, when we find the root of this new function, it will be our desired x value. Then it finds the derivative f'(x) by finding the slope between two points on the function. Then, the values are simply inserted into Newton's method which states for an approximation of the root x, x=x-(f(x)/f'(x)) (in the code, we use 0 as an initial x value). Since this finds the roots, it finds our x value. And since the equation is guaranteed to be linear, the approximation will be exact.

93 bytes

Mathcad, [uses built-in]

Mathcad has two built-in methods of solving such equations:

Symbolic solver (uses the keyword solve)
Solve Block (which works in both numeric and symbolic modes). A Solve Block starts with the keyword Given, followed a set of expressions defining the conditions of interest, and closed by one of the solving keywords, such as Find (which finds an exact solution) or MinErr (which minimizes the error between the target and any solution).

The symbolic solver is quite happy with y=x and returns the solution x = y.
For those unfamiliar with Mathcad, the image below is taken directly from the WYSIWYGish Mathcad 15 workbook.  Changing any of the expressions where they are written will cause Mathcad to reevaluate its answer and update the display accordingly.

Out of idle curiosity, why the downvotes?  I can grasp that the simplicity of it may be at the root of it, but it appears in essence to be no different than the TI Basic solution, which merely adds a small amount of input processing before calling the built-in solver and yet that wasn't downvoted.

What is the actual byte count of this program?

The downvotes are likely because your solution is trivial - see 'What is a trivial solution?' on meta.

Axiom, 214 bytes [uses built-in]
q(t:EQ POLY FLOAT):Any==(a:=[variables(lhs t),variables(rhs t)];a.1~=[x]and a.1~=[]=>%i;a.2~=[x]and a.2~=[]=>%i;a.1=[]and a.2=[]=>%i;a.1=[x]and degree(lhs t,x)>1=>%i;a.2=[x]and degree(rhs t,x)>1=>%i;rhs solve(t).1)

For some error would return %i, for other type of errors the function is stopped from the system, something else as 1--2 seems out of language... test:
(72) -> q(x+3=9)
   (72)  6.0
                                  Type: Complex Fraction Polynomial Float
(73) -> q(3+4=x)
   (73)  7.0
                                  Type: Complex Fraction Polynomial Float
(74) -> q(4+x=5)
   (74)  1.0
                                  Type: Complex Fraction Polynomial Float
(75) -> q(3+3*3=x)
   (75)  12.0
                                  Type: Complex Fraction Polynomial Float
(76) -> q(3*x-4=7+2*x)
   (76)  11.0
                                  Type: Complex Fraction Polynomial Float
(77) -> q(3--1=x)
  Line   1: q(3--1=x)
           .AB
  Error  A: Missing mate.
  Error  B: syntax error at top level
  Error  B: Possibly missing a )
   3 error(s) parsing
(77) -> q(3*(2+4*x)=7*x-4)
   (77)  - 2.0
                                  Type: Complex Fraction Polynomial Float
(78) -> q(1.2+2.3*x=5.8)
   (78)  2.0
                                  Type: Complex Fraction Polynomial Float
(79) -> q(10=4*x)
   (79)  2.5
                                  Type: Complex Fraction Polynomial Float
(80) -> q((5)(4)=x)
   Cannot find a definition or applicable library operation named 5
      with argument type(s)
                           PositiveInteger

  Perhaps you should use "@" to indicate the required return type,
  or "$" to specify which version of the function you need.
(80) -> q(5(x+3)=2 )
   (80)  %i
                                                    Type: Complex Integer
(81) -> q(x=y)
   (81)  %i
                                                    Type: Complex Integer
(82) -> q(4=3)
   (82)  %i
                                                    Type: Complex Integer
(83) -> q(x+3=x-7)
   >> Error detected within library code:
   inconsistent equation
protected-symbol-warn called with (NIL)
(83) -> q(x=x)
   >> Error detected within library code:
   equation is always satisfied
protected-symbol-warn called with (NIL)

Vyxal, 6 bytes [uses built-in]
\=/÷∆q

Try it Online!
As a bonus, it can even handle some of the invalid input cases.
Explained
\=/÷∆q
\=/÷   # Split the input on "=" and dump to the stack
    ∆q # Pop two items a and b and solve x in a = b

Python, 134 bytes [uses built-in]
import re
def f(e):
    l,r=re.sub(r"(?<=\d)x","*x",e).split("=")
    a,b=[eval(f"{l}-({r})",{"x":x})for x in[0,1]]
    return a/(a-b)

Attempt This Online!
This preprocesses the string, turns it into an expression where \$x\$ is the root, then uses eval to find two points plus basic algebra to find the root.


text:
Sorting rectangular matrices
Given a matrix A, we can say that it is "sorted" if each row and column of A is sorted (ascending left-to-right for rows and top-to-bottom for columns). Thus, this matrix is sorted:
[ 1 2 3 4 5 ]
[ 2 2 3 4 5 ]
[ 3 3 3 4 5 ]
[ 4 4 4 4 5 ]
[ 5 5 5 5 5 ]

However, this matrix is not sorted:
[ 1 2 3 4 5 ]
[ 2 1 3 4 5 ]
[ 3 3 3 4 5 ]
[ 4 5 4 5 5 ]
[ 5 5 5 5 5 ]

The second column (transpose of [2, 1, 3, 5, 5]) and fourth row ([4, 5, 4, 5, 5]) are not sorted in ascending order.
Given a matrix (either as a 2D rectangular nested list or a string with consistent, distinct delimiters between rows and between values) and optionally the width and/or height of the matrix, output a sorted matrix (in the same format) with the same dimensions and containing the same values as the input matrix.
The values in the matrix will always be in the inclusive range [-128, 127] (8-bit signed two's complement integers). There is no limit on the dimensions of the input matrix.
Examples
Because there are multiple valid outputs for each input, these are possible outputs. Any output that fulfills the conditions is valid. The examples are given with Python list notation.
[[0, -29]] -> [[-29, 0]]
[[-36, -18, 0], [8, 99, 112], [14, 6, -12]] -> [[-36, -18, 0], [-12, 6, 14], [8, 99, 112]]
[[-20, -102, -41, -57, -73, 58], [49, 82, 60, -53, 58, 60], [-32, -127, -23, -70, -46, -108], [-56, -15, 98, -90, 73, -67], [97, 74, 59, 126, -7, 46], [-101, 42, -39, -52, 89, 29]] -> [[-127, -108, -101, -70, -53, -32], [-102, -90, -67, -52, -23, 42], [-73, -57, -46, -20, 46, 59], [-56, -41, -15, 49, 60, 74], [-39, -7, 58, 60, 82, 97], [29, 58, 73, 89, 98, 126]]
[[23, 82, 94, 7, -39, 70, -31, -120], [-13, 78, -70, 28, -10, 30, 101, 48], [60, -111, 32, 93, 91, 77, -27, 7], [-37, -41, -8, 80, 102, 18, -16, -48], [97, -14, -102, -53, 108, -92, -83, 108], [-67, -121, -15, -9, 91, -89, -127, -109], [-127, -103, -48, -2, -106, 3, -114, 97], [28, -78, -40, 52, 39, 115, -88, 10]] -> [[-127, -127, -120, -109, -92, -70, -40, -14], [-121, -114, -106, -89, -67, -39, -13, 7], [-111, -103, -88, -53, -37, -10, 10, 32], [-102, -83, -48, -31, -9, 18, 39, 77], [-78, -48, -27, -8, 23, 48, 78, 91], [-41, -16, -2, 28, 52, 80, 93, 97], [-15, 3, 28, 60, 82, 94, 101, 108], [7, 30, 70, 91, 97, 102, 108, 115]]
[[85, 90, -65, -38, -58, -71, 123, -83, 44], [55, -34, 21, 103, -10, 59, -109, 30, -41], [108, -106, -90, 74, 117, 15, -63, 94, -37], [43, -118, -126, -45, 77, -62, 22, 76, 9], [56, 31, 58, 51, -64, 125, -48, -123, -108], [77, -53, -61, 99, -16, -21, -98, -50, 60], [127, -113, -9, 33, -6, -102, -47, -122, 31], [-59, -23, 0, 21, 14, 61, 83, 47, -6], [97, -120, -111, 113, -68, -128, -81, 68, 88]] -> [[-128, -126, -122, -113, -106, -81, -62, -47, -16], [-123, -120, -111, -102, -71, -61, -45, -10, 21], [-118, -109, -98, -68, -59, -41, -9, 21, 44], [-108, -90, -65, -58, -38, -6, 22, 47, 60], [-83, -64, -53, -37, -6, 30, 51, 61, 77], [-63, -50, -34, 0, 31, 55, 68, 83, 94], [-48, -23, 9, 31, 56, 74, 85, 97, 108], [-21, 14, 33, 58, 76, 88, 99, 113, 123], [15, 43, 59, 77, 90, 103, 117, 125, 127]]
[[-80, -42, 1, 126, -42, -34, 81, 73, 6, 9, 72], [-98, -98, -82, 63, -16, -116, 29, 61, 119, 20, 19], [-99, -70, 41, 44, 117, 61, 89, -117, 92, -3, -49], [18, 122, 126, 84, 79, 114, -61, 45, 80, 109, -107], [-77, 73, -62, -58, -25, -24, 126, -14, -13, -90, -60], [84, 1, 95, 21, -13, 26, 75, 78, -36, -76, -91], [54, -58, 79, -128, 63, 119, 79, 106, 103, 125, 98], [126, 37, -77, -15, -57, 63, 22, -98, 93, 67, 41], [93, -45, -91, 34, 29, -38, -103, 109, -92, 6, -115], [32, -112, -29, -65, 61, 20, 80, -41, -68, 28, 25], [56, -112, 47, -88, 56, -35, -26, 13, 122, 27, -70], [108, -69, -42, 24, 94, -20, -46, 90, -98, 112, 32]] -> [[-128, -117, -115, -107, -98, -91, -77, -62, -45, -29, -3], [-116, -112, -103, -98, -90, -76, -61, -42, -26, 1, 21], [-112, -99, -98, -88, -70, -60, -42, -25, 1, 22, 34], [-98, -92, -82, -70, -58, -42, -24, 6, 24, 37, 61], [-91, -80, -69, -58, -41, -20, 6, 25, 41, 61, 73], [-77, -68, -57, -38, -16, 9, 26, 41, 61, 75, 81], [-65, -49, -36, -15, 13, 27, 44, 63, 78, 84, 93], [-46, -35, -14, 18, 28, 45, 63, 79, 84, 94, 108], [-34, -13, 19, 29, 47, 63, 79, 89, 95, 109, 117], [-13, 20, 29, 54, 67, 79, 90, 98, 109, 119, 122], [20, 32, 56, 72, 80, 92, 103, 112, 119, 125, 126], [32, 56, 73, 80, 93, 106, 114, 122, 126, 126, 126]]
[[53, 109, -41, 66, 63, -108, -24, 85, 28, 57, -11, -94, -16], [-28, -113, 58, 115, -28, -124, 71, -109, -65, 45, 75, 97, 107], [124, 23, 101, 112, -64, 19, 21, 34, 6, -2, -70, -92, 122], [19, 94, 80, -105, -3, -125, -2, 44, -24, 41, -30, 64, 32], [36, -44, 59, -28, -36, -11, 111, -64, 78, 120, 1, 102, 49], [-128, 67, 17, -9, -64, -86, 117, 7, 118, 7, -11, -82, 124], [5, -36, 22, 98, -78, -33, 100, 92, -55, 125, -28, 24, -6], [97, 31, -106, -15, 8, 80, -86, -107, -105, -5, -71, 76, 124], [-83, 24, -116, 66, 82, -32, -19, 111, -84, -77, -14, 67, -70], [77, -111, -101, -91, -23, 36, 24, -33, 13, -90, -9, 32, -54], [51, -31, 125, -25, -61, 5, 71, -81, -3, -39, 109, -17, -97], [61, -46, -122, 76, 13, -101, 24, 97, 39, -29, -22, -3, -116], [56, 0, -4, 71, -116, 115, 79, -83, 74, 44, -77, 42, -30], [-72, 45, -109, -82, 43, 38, -117, 1, 69, -66, -18, 108, 8]] -> [[-128, -125, -122, -116, -109, -105, -92, -83, -71, -55, -32, -24, -9], [-124, -117, -116, -109, -105, -91, -82, -70, -54, -31, -23, -9, 5], [-116, -113, -108, -101, -90, -82, -70, -46, -30, -22, -6, 5, 22], [-111, -107, -101, -86, -81, -66, -44, -30, -19, -5, 6, 23, 36], [-106, -97, -86, -78, -65, -41, -29, -18, -4, 7, 24, 38, 51], [-94, -84, -77, -64, -39, -28, -17, -3, 7, 24, 39, 53, 66], [-83, -77, -64, -36, -28, -16, -3, 8, 24, 41, 56, 67, 76], [-72, -64, -36, -28, -15, -3, 8, 24, 42, 57, 67, 76, 85], [-61, -33, -28, -14, -2, 13, 28, 43, 58, 69, 77, 92, 100], [-33, -25, -11, -2, 13, 31, 44, 59, 71, 78, 94, 101, 109], [-24, -11, 0, 17, 32, 44, 61, 71, 79, 97, 102, 111, 115], [-11, 1, 19, 32, 45, 63, 71, 80, 97, 107, 111, 117, 122], [1, 19, 34, 45, 64, 74, 80, 97, 108, 112, 118, 124, 124], [21, 36, 49, 66, 75, 82, 98, 109, 115, 120, 124, 125, 125]]
[[47, -58, 7, -88, 126, -87, 103, 125, 83, 32, 116, 107, -92, -96, 110, -102], [-75, -81, 53, -93, 91, -5, -4, 104, 88, -73, -114, -113, 126, 78, -114, -3], [125, -68, -88, -17, 1, 53, -124, -59, -19, 87, -60, 55, -30, -6, 39, 37], [-38, -123, 125, 119, -43, 11, -25, -89, -57, 112, 123, 9, -76, -125, 118, 68], [-119, -97, -42, 73, 80, 108, -96, -54, -110, 115, -58, -67, -9, 94, 71, -56], [-25, 109, -51, 71, 61, 12, 122, -99, -16, -87, -127, -76, 46, 102, 52, 114], [97, 26, -112, 49, -44, -26, -93, -119, 21, 101, 83, -112, 14, 41, 120, 37], [90, 95, 89, 73, 51, -33, 3, -125, -106, -83, -5, -26, 33, -119, -74, 41], [9, -81, 116, -124, -8, -15, 65, 104, 41, -92, 2, 51, 33, 115, -47, 30], [87, -127, 121, 42, 33, -22, 28, -74, 26, 55, 126, -70, 0, -63, -40, -51], [-117, 79, -113, -4, 78, -33, -54, -40, -1, -48, 60, 91, 119, 117, -75, 114], [7, 102, 6, 77, -112, -128, 34, 112, -82, -17, -120, -96, -101, -79, -27, -84], [-74, -77, 67, -78, -72, 80, 59, 115, -76, -7, 66, -28, 120, 117, 56, -46], [80, 42, -121, -5, 73, -82, -115, -72, 10, -120, -26, -82, -22, 110, -7, -119], [10, -88, 39, 92, -16, 58, -40, 79, 116, 75, 96, -102, 4, 93, 46, -95], [20, -61, 110, 18, -103, -87, -67, -26, -74, -22, 1, -106, -81, -20, 10, 87]] -> [[-128, -127, -125, -124, -120, -117, -112, -102, -95, -87, -81, -74, -59, -43, -26, -7], [-127, -125, -123, -119, -115, -112, -102, -93, -87, -79, -74, -58, -42, -25, -7, 6], [-124, -121, -119, -114, -112, -101, -93, -87, -78, -73, -58, -40, -25, -6, 7, 26], [-120, -119, -114, -110, -99, -92, -84, -77, -72, -57, -40, -22, -5, 7, 28, 41], [-119, -113, -106, -97, -92, -83, -76, -72, -56, -40, -22, -5, 9, 30, 42, 55], [-113, -106, -96, -89, -82, -76, -70, -54, -38, -22, -5, 9, 32, 42, 56, 73], [-103, -96, -88, -82, -76, -68, -54, -33, -20, -4, 10, 33, 46, 58, 73, 80], [-96, -88, -82, -75, -67, -51, -33, -19, -4, 10, 33, 46, 59, 73, 83, 91], [-88, -81, -75, -67, -51, -30, -17, -3, 10, 33, 47, 60, 75, 83, 92, 102], [-81, -74, -63, -48, -28, -17, -1, 11, 34, 49, 61, 77, 87, 93, 103, 110], [-74, -61, -47, -27, -16, 0, 12, 37, 51, 65, 78, 87, 94, 104, 110, 115], [-60, -46, -26, -16, 1, 14, 37, 51, 66, 78, 87, 95, 104, 112, 115, 117], [-44, -26, -15, 1, 18, 39, 52, 67, 79, 88, 96, 107, 112, 116, 118, 120], [-26, -9, 2, 20, 39, 53, 68, 79, 89, 97, 108, 114, 116, 119, 121, 125], [-8, 3, 21, 41, 53, 71, 80, 90, 101, 109, 114, 116, 119, 122, 125, 126], [4, 26, 41, 55, 71, 80, 91, 102, 110, 115, 117, 120, 123, 125, 126, 126]]
[[-88, -62, -59, -18, 118, -13, -93, 75, 44, 67, -122, -1, 117, -121, 118, 13, -33, 44], [-4, -75, 95, 25, 9, -104, 6, 79, -110, 3, -108, 117, 96, 113, 69, 55, 75, -95], [-69, 11, 87, -78, -18, -17, -52, 6, 88, 31, 39, 45, 61, -75, -83, 117, 85, -3], [-27, 83, -86, -69, -29, -15, 62, -90, -127, 53, -71, 77, -95, -86, -20, 69, 103, -111], [3, -6, -70, -121, -58, -72, 88, 105, 68, -31, 86, -28, 69, 78, 13, 88, 19, 75], [69, 73, 116, -2, -93, 15, 74, 58, 98, -100, -54, 95, 47, -126, -71, 63, 84, 113], [110, -42, -33, -87, 109, 86, -75, 25, 83, -25, -76, 84, -42, -57, -93, -9, -90, 3], [-100, 36, -83, 10, -85, 88, -15, 107, -76, -37, 109, 79, -120, 118, -60, 113, -124, -15], [123, 122, -94, 14, -16, 118, -57, -111, 80, 62, 56, 66, 27, -44, -53, -13, 94, -28], [116, -67, 8, -70, -54, -1, 53, 40, -78, 15, -121, -30, -125, -16, -74, 119, 97, 43], [-24, 109, -72, 16, 55, -51, -87, 46, -62, 69, -106, -49, -112, 71, -55, 104, -110, 62], [67, 13, -75, 106, -35, -54, 15, -104, 34, 93, 39, -126, -29, 61, 29, 4, 70, -28], [27, -89, -15, -32, -82, -72, 53, -22, -23, 49, -16, 76, -25, 31, 115, -88, -57, -97], [1, 29, 54, 88, 86, 77, -58, 100, -125, 117, 102, 41, 99, 115, 24, -16, -99, -116], [-85, -47, -108, 26, 18, -107, -88, 110, 27, -118, 88, -122, -85, -94, -33, 51, 40, 77], [-3, 52, -20, 12, 117, 101, 34, -8, -100, -23, 45, 83, -88, -90, -47, 70, 29, -111], [26, -68, 7, 38, -118, -53, -79, -48, 41, -88, 35, 86, 66, 24, 37, 72, -66, -77]] -> [[-127, -126, -125, -122, -121, -112, -108, -100, -93, -88, -83, -75, -68, -54, -37, -25, -15, 4], [-126, -125, -122, -120, -111, -108, -100, -93, -88, -83, -75, -67, -54, -35, -24, -15, 6, 18], [-124, -121, -118, -111, -107, -99, -93, -88, -82, -74, -66, -54, -33, -23, -13, 6, 19, 34], [-121, -118, -111, -106, -97, -90, -87, -79, -72, -62, -53, -33, -23, -13, 7, 24, 34, 45], [-116, -110, -104, -95, -90, -87, -78, -72, -62, -53, -33, -22, -9, 8, 24, 35, 45, 58], [-110, -104, -95, -90, -86, -78, -72, -60, -52, -32, -20, -8, 9, 25, 36, 46, 61, 69], [-100, -94, -89, -86, -77, -71, -59, -51, -31, -20, -6, 10, 25, 37, 47, 61, 69, 75], [-94, -88, -85, -76, -71, -58, -49, -30, -18, -4, 11, 26, 38, 49, 62, 69, 76, 83], [-88, -85, -76, -70, -58, -48, -29, -18, -3, 12, 26, 39, 51, 62, 69, 77, 84, 88], [-85, -75, -70, -57, -47, -29, -17, -3, 13, 27, 39, 52, 62, 70, 77, 84, 88, 96], [-75, -69, -57, -47, -28, -16, -2, 13, 27, 40, 53, 63, 70, 77, 85, 88, 97, 104], [-69, -57, -44, -28, -16, -1, 13, 27, 40, 53, 66, 71, 78, 86, 88, 98, 105, 110], [-55, -42, -28, -16, -1, 14, 29, 41, 53, 66, 72, 79, 86, 88, 99, 106, 110, 115], [-42, -27, -16, 1, 15, 29, 41, 54, 67, 73, 79, 86, 93, 100, 107, 113, 116, 117], [-25, -15, 3, 15, 29, 43, 55, 67, 74, 80, 86, 94, 101, 109, 113, 116, 117, 118], [-15, 3, 15, 31, 44, 55, 68, 75, 83, 87, 95, 102, 109, 113, 117, 117, 118, 119], [3, 16, 31, 44, 56, 69, 75, 83, 88, 95, 103, 109, 115, 117, 118, 118, 122, 123]]
[[84, 18, -122, 74, -47, 17, -69, 121, -79, 110, 10, 122, 84, 19, 77, -57, 25, 87, -42], [95, 89, 10, -1, -24, -93, -26, -39, 11, -15, 47, 23, 114, 36, 121, -87, 106, 120, -86], [48, 66, 65, 28, 74, -22, -67, 77, -77, 19, 88, -24, -88, 85, -34, 13, 103, -102, 86], [108, -17, -122, -13, 63, 61, -56, 24, -48, -3, -85, -57, 11, -52, -26, -24, 48, 100, 18], [-91, -126, 124, 5, -118, 93, 94, -100, -24, 15, 77, -43, 64, 51, 64, 7, -22, -47, 79], [98, 80, 117, -19, -55, -95, -35, -48, -56, -122, -120, 52, 54, 37, -101, -38, -35, 101, -6], [72, 68, 26, -79, -1, 25, -3, -40, 2, 56, 119, 17, -95, 83, -94, -79, -88, -110, 85], [55, 39, 75, 127, 110, 0, 56, -1, 39, 116, 44, 120, -113, 81, 113, 10, 78, 114, -79], [103, 121, 78, -121, -17, 33, 117, 110, -26, 2, -79, 27, -117, 62, -27, -17, -20, 104, 115], [-11, 67, 76, 62, -14, 78, -94, -8, -71, 15, 77, 98, 127, 109, 61, 33, -51, 65, -103], [-91, 97, 83, -61, 22, -31, 20, -119, 40, -48, -3, 34, -70, 23, -80, -73, 5, 23, -102], [109, 78, 124, 118, -39, -3, -114, -50, 0, 79, -68, -34, -96, 104, -120, 41, 2, 108, -17], [-90, -30, -25, -29, -52, -37, -49, 20, 91, -48, -91, 80, -117, -6, -88, -68, 69, 103, 118], [-79, -118, -122, -112, 71, -4, 28, 78, -77, -33, 10, 21, -125, 69, -88, 18, 99, 11, -127], [-124, -53, -4, 80, -94, -44, -124, 94, 97, -55, -89, -78, -37, -38, -40, -11, -116, 84, 18], [44, 32, -44, 76, -101, 85, -67, 69, -4, 20, -89, -103, 117, 18, -121, 84, 18, -91, -106], [107, 58, 6, -72, 112, 96, 39, 77, -4, 104, 60, 112, 39, -102, -4, -11, 80, 36, -117], [96, -79, 119, -65, 80, -35, -60, 4, -63, 92, 76, -46, -2, 59, -86, -105, -76, 106, -102], [-88, -89, 69, -5, 63, 75, -59, -93, 101, 33, 64, 114, -126, -106, 33, 113, 50, 71, 82], [-94, 9, -3, 11, 115, -121, 111, -34, -11, 96, -34, 51, -44, -56, -20, -14, 1, 49, 100]] -> [[-127, -126, -125, -122, -121, -119, -116, -105, -101, -93, -88, -79, -71, -57, -48, -38, -26, -14, -3], [-126, -124, -122, -121, -118, -114, -103, -100, -93, -88, -79, -70, -56, -48, -37, -26, -14, -3, 10], [-124, -122, -121, -118, -113, -103, -96, -91, -88, -79, -69, -56, -47, -37, -25, -13, -3, 10, 19], [-122, -120, -117, -112, -102, -95, -91, -88, -79, -68, -56, -47, -35, -24, -11, -2, 10, 19, 33], [-120, -117, -110, -102, -95, -91, -88, -79, -68, -55, -46, -35, -24, -11, -1, 10, 20, 33, 48], [-117, -106, -102, -94, -91, -87, -79, -67, -55, -44, -35, -24, -11, -1, 11, 20, 33, 48, 62], [-106, -102, -94, -90, -86, -78, -67, -53, -44, -34, -24, -11, -1, 11, 20, 33, 49, 62, 69], [-101, -94, -89, -86, -77, -65, -52, -44, -34, -22, -8, 0, 11, 21, 34, 50, 63, 71, 77], [-94, -89, -85, -77, -63, -52, -43, -34, -22, -6, 0, 11, 22, 36, 51, 63, 71, 77, 80], [-89, -80, -76, -61, -51, -42, -34, -20, -6, 1, 13, 23, 36, 51, 64, 72, 78, 81, 86], [-79, -73, -60, -50, -40, -33, -20, -5, 2, 15, 23, 37, 52, 64, 74, 78, 82, 87, 96], [-72, -59, -49, -40, -31, -19, -4, 2, 15, 23, 39, 54, 64, 74, 78, 83, 88, 96, 101], [-57, -48, -39, -30, -17, -4, 2, 17, 24, 39, 55, 65, 75, 78, 83, 89, 97, 103, 107], [-48, -39, -29, -17, -4, 4, 17, 25, 39, 56, 65, 75, 78, 84, 91, 97, 103, 108, 111], [-38, -27, -17, -4, 5, 18, 25, 39, 56, 66, 76, 79, 84, 92, 98, 103, 108, 112, 114], [-26, -17, -4, 5, 18, 26, 40, 58, 67, 76, 79, 84, 93, 98, 104, 109, 112, 115, 117], [-15, -3, 6, 18, 27, 41, 59, 68, 76, 80, 84, 94, 99, 104, 109, 113, 115, 118, 120], [-3, 7, 18, 28, 44, 60, 69, 77, 80, 85, 94, 100, 104, 110, 113, 116, 118, 120, 121], [9, 18, 28, 44, 61, 69, 77, 80, 85, 95, 100, 106, 110, 114, 117, 119, 121, 122, 124], [18, 32, 47, 61, 69, 77, 80, 85, 96, 101, 106, 110, 114, 117, 119, 121, 124, 127, 127]]

Huge thanks to Sp3000 for helping me out with this challenge in chat

Your examples seem to have always the same input as ouptut, perhaps you might want to add some where the input is not equal to the output? =)

@flawr Whoops, there was a bug in the script I was using to generate the test cases. I've fixed it now.

Jelly, 3 bytes
FṢs

Takes matrix and width as left and right arguments. Try it online!
How it works
FṢs  Main link. Arguments: M (matrix), w (width)

F    Flatten M.
 Ṣ   Sort.
  s  Split into rows of width w.

Retina, 8 6 5 bytes
Thanks to randomra for saving 3 bytes.
O#`.+

Input format is a bit awkward. Both the delimiter within rows and between rows needs to consist of line-terminating characters (i.e. those not matched by .). E.g. you could use single linefeeds within rows and double linefeeds between rows. Output is printed in the same format.
Try it online!
Explanation
The perfect challenge to show off Retina's latest addition: sort stages!
Sort stages work as follows: the regex is matched against the entire string. The matches are then the things that are being sorted, whereas everything around them is treated as "list delimiters" and left unchanged. This challenge can be solved if we treat the input as a flat list, sort that and reshape it into the original matrix form. That's exactly how sort stages work, except there are no explicit steps for flattening and reshaping - Retina just ignores the 2D structure altogether.
As for this code in particular, the regex is .+ which simply matches all runs of non-linefeed characters, which is all the numbers due to the input format. By default, the matches are sorted lexicographically, but the # option tells Retina to sort them numerically (by the first signed integer that appears in the match).
For three additional bytes, this could support any input format whatsoever, by using the regex -?\d+.

Now I know for sure that Retina is a golfing language. I wasn't sure earlier. Looked totally general-purpose. Well maybe the decimal->unary->decimal stuff was kinda giving it away, but I know now.

That is awesome. Is it possible to do this without using a builtin sort?

@CatsAreFluffy Quoting the docs, "Retina was mainly developed for code golf...". That said I don't understand a) how "golfing language" and "general purpose" language are mutually exclusive, b) how Retina, being based entirely on regex processing, was ever general-purpose in the first place and c) how adding a built-in for sorting makes it any less general-purpose.

@MamaFunRoll Sure, Retina is and was Turing-complete. It's going to be pretty painful though. You'd have to convert the integers to unary, and take care of the sign one way or another (e.g. with unary +1 and -1 digits). Then you could bubble sort the list by repeatedly matching pairs x...y with x > y and replacing it with y...x. Then convert unary back to decimal.

@MartinBüttner Yeah, that was intended as a joke.

Pyth, 6 5 bytes
1 byte thanks to DenkerAffe
cSsQE

Demonstration
Input is the matrix, followed by its width.
To sort the matrix, I simply flatten it into a list, sort the list, and chop it into a matrix again. Since every subsequence of a sorted list is sorted, this results in a sorted matrix.

Python, 43 bytes
lambda M:eval("map(sorted,zip(*"*2+"M))))")

The interesting question is how to apply mapsort-transpose twice. The shortest I found was to eval a string that has it twice. Compare some alternatives:
lambda M:eval("map(sorted,zip(*"*2+"M))))")
lambda M:map(sorted,zip(*map(sorted,zip(*M))))
s="map(sorted,zip(*%s))";lambda M:eval(s%s%M)
g=lambda M:map(sorted,zip(*M));lambda M:g(g(M))
f=lambda M,n=-1:n*M or f(map(sorted,zip(*M)),n+1)
def f(M):exec"M=map(sorted,zip(*M));"*2;return M

(The second and fourth can be shortened by 1 byte by aliasing sorted, but it's not enough.)
An alternative approach of converting to 1D, sorting, and reshaping to 2D, is very close, at 44 bytes. The width w is taken as an input.
lambda M,w:zip(*[iter(sorted(sum(M,[])))]*w)

Pyth, 7 bytes
CSMCSMQ

Try it here!
First we sort all rows of the matrix, transpose the result, sort all rows again and transpose it back.

CJam, 8 bytes
{:$z:$z}

Try it online!
An unnamed block which expects a matrix on the stack and leaves the sorted matrix on the stack.
Also just sorts each row (:$), transposes the result (z), sorts again and transposes it back.

JavaScript (ES6), 67 bytes
a=>a.map(b=>c.splice(0,b.length),c=[].concat(...a).sort((d,e)=>d-e))

Port of @isaacg's Pyth answer.

Octave, 19 bytes
Isn't nice when two programs fulfill the requirement

@(a)sort(sort(a')') % or
@(a)sort(sort(a)')'

Anonymous function that transposes the matrix twice to get the original dimensions back. I'm going to claim that this will be the shortest entry in a non-golfing language. Let's see if anyone proves me wrong :)

Mathematica, 26 bytes
Nest[Sort@*Transpose,#,2]&

Function names are long. That sucks.

When you have builtins for recognizing upside down goats, it's okay to have long names. :P

APL, 11 9 bytes
⍴⍴⊂∘⍋∘,⌷,

Hooks of three functions composed together :).
example:
    (⍴⍴⊂∘⍋∘,⌷,) 2 2⍴10 5 4 8
4  5
8 10

RETURN, 10 bytes
[{␇␌}␅␆␎␉]

Try it here.
Anonymous lambda that leaves result on stack. Usage:
""{1 2 3 4}""{1 3 4 2}""{4 1 2 3}""{3 1 2 4}[{␇␌}␅␆␎␉]!

Explanation
[            ]  lambda
 {␇␌}          push matrix width to stack2
      ␅␆      flatten, sort
          ␎␉   chunk by matrix width (popped from stack2)

MATL, 4 bytes
S!S!

Try it online!
This just sorts (S) column-wise (sorting the contents of each column seperately) then transposes (!) and sorts the input again, quite straightforward. This program needs a semicolon (;) instead of a comma (,) as delimiter of rows.

Python 3, 52 bytes
A solution using numpy
from numpy import*
lambda s:sort(sort(array(s)).T).T

(sort(s,None) is longer as we need to reshape after sort)
Results
>>> f([[-5, -4, -3, -2, -1, 0], [-60, -70, -80, -9, 100, 110], [5, 4, 3, 2, 1, 0], [6, 7, 8, 9, 10, 11]])
array([[-80, -70, -60,  -9,  -1,   0],
       [ -5,  -4,  -3,  -2,   4,   5],
       [  0,   1,   2,   3,  10,  11],
       [  6,   7,   8,   9, 100, 110]])

Ruby, 42 bytes
(m,w)->{m.flatten.sort.each_slice(w).to_a}

Arguments are the matrix and its width.  It works exactly like it reads :)

Perl 6, 28 25 bytes
{.flat.sort.rotor(+.[0])}

This takes a list of lists (not arrays).

CJam, 6 bytes
{e_$/}

This is a code block (unnamed function) that expects the width and matrix on the stack, pops them and pushes the sorted matrix in return. Try it online!
How it works
     e# STACK: w (width), M (matrix)
     e#
e_   e# Flatten M.
  $  e# Sort the resulting, flat array.
   / e# Split the sorted array into rows of length w.

C, 39 Bytes
f(x,m,n){qsort(x,m*n,4,"YZZ+QQQÃ");}

If the out-of-range char can't show use this instead, though longer
f(x,m,n){qsort(x,m*n,4,"YZ\x8B\2Z+\2QQQ\xC3");}

Usage:
int m, n, i, j;
scanf ("%d%d", &m, &n);
int arr[m][n];
for (i=0; i<m; i++) {
    for (j=0; j<n; j++) {
        scanf("%d", &arr[i][j]);
    }
}
f(arr,m,n);
for (i=0; i<m; i++) {
    for (j=0; j<n; j++) {
        printf("%d ", arr[i][j]);
    }
    puts("");
}

Text's disassembler:

00000000:  59                         POP     ECX
00000001:  5A                         POP     EDX
00000002:  8B02                       MOV     EAX,[EDX]
00000004:  5A                         POP     EDX
00000005:  2B02                       SUB     EAX,[EDX]
00000007:  51                         PUSH    ECX
00000008:  51                         PUSH    ECX
00000009:  51                         PUSH    ECX
0000000A:  C3                         RETN

Uiua, 7 bytes
⍜♭(⊏⍏.)

Try it!
⍜♭(⊏⍏.)
⍜♭(   )  # under deshape (apply a function to a flattened array, but keep the shape)
   ⊏⍏.   # sort

Japt v2.0a0, 4 bytes
mÍyÍ

Try it

Clojure, 39 bytes
(fn[M w](partition w(sort(flatten M))))

M is a nested list (the matrix) and w is its width (number of columns).
(f [[1 3 2 3][5 1 3 7][4 3 6 5]] 4)

((1 1 2 3)
 (3 3 3 4)
 (5 5 6 7))