Сортирование матрицы (двухмерного массива) Java?

Если вы планируете сортировать матрицу, то конечно эффективней будет хранить её в виде одномерного массива, чтоб можно было эффективно отсортировать его с помощью быстрой сортировки реализованной методе sort в класса java.util.Arrays.

А чтоб с массивом можно было работать как с матрицей, можно реализовать класс-адаптер

import java.util.Arrays;

public class IntMatrix {
		private final int[] lineMatrix;
		private final int n;
		private final int m;

		public IntMatrix(int[] lineMatrix, int n, int m) {

			if (n < 0 || m < 0 || lineMatrix.length != n * m)
				throw new IllegalArgumentException();

			this.lineMatrix = lineMatrix.clone();
			this.n = n;
			this.m = m;
		}

		public int get(int i, int j) {
			if (i < n && j < m)
				return lineMatrix[i * m + j];
			else
				throw new ArrayIndexOutOfBoundsException();
		}

		public void set(int value, int i, int j) {
			if (i < n && j < m)
				lineMatrix[i * m + j] = value;
			else
				throw new ArrayIndexOutOfBoundsException();
		}

		public  void sort() {
			// готовая реализация быстрой сортировки
			Arrays.sort(lineMatrix);
		}

		public int getN() {
			return n;
		}

		public int getM() {
			return m;
		}
	}

Пример использования

public static void main(String[] args) {


		int n = 10, m = 15;

		IntMatrix intMatrix = new IntMatrix(new int[n * m], n, m);

		fillMatrixByRandomValues(intMatrix);

		printMatrix(intMatrix);

		intMatrix.sort();

		System.out.println("---------------");

		printMatrix(intMatrix);
	}


	/** заполнение матрицы случайными числами */
	static void fillMatrixByRandomValues(IntMatrix matrix) {
		Random random = new Random();
		for (int i = 0; i < matrix.getN(); i++) {
			for (int j = 0; j < matrix.getM(); j++) {
				matrix.set(random.nextInt(1000), i, j);
			}
		}
	}

	/** печать матрицы в консоль */
	static void printMatrix(IntMatrix matrix) {
		for (int i = 0; i < matrix.getN(); i++) {
			for (int j = 0; j < matrix.getM(); j++) {
				System.out.printf("%s\t", matrix.get(i , j));
			}
			System.out.println();
		}
	}

Линейный массив будет занимать меньше места, чем двумерный. Сортировка реализованная в классе java.util.Arrays хорошо и по скорости и по расходу памяти.