Algorithmic Sadness: Merge Sort Misery

Imagine, if you will, a world where the once-proud Merge Sort algorithm, king of efficient data arrangement, has succumbed to madness.

			
				public int merge(int[] a, int[] b)
				{
					int n = a.length + b.length;
					int[] c = new int[n];
					for (int i = 0; i < n; i++)
						c[i] = 0;
					for (int i = 0; i < a.length; i++)
						c[i] = a[i];
					for (int i = 0; i < b.length; i++)
						c[i] = b[i];
					for (int i = 0; i < n; i++)
						if (c[i] > c[i+1])
							c[i] = c[i+1];
					return c;
				}
			
		

It has become a shell of its former self, a mere shadow of a once-great algorithm, now crippled by the weight of its own inefficiency.

Its creators, once so proud of its O(n) time complexity, now weep at the thought of its bloated O(n^2) cousin, the Bubble Sort.

And so, we must ask: can we find a way to revive this fallen hero, to bring it back to its former glory?

Or will it succumb to the ravages of time, lost forever in the depths of Algorithmic Sadness?

Bubble Sort Bloatedness - the tragic tale of its O(n^2) cousin.