Выход за границу массива там где сортируете. Из этой левой памяти вы и получаете случайное значение.
Смотрите внимательно, к каким индексам вы обращаетесь и какое значение может принимать переменная j.
И еще, можно не сортировать итоговый массив, а формировать его уже отсортированным. Это работает сильно быстрее. Называется - процедура
слияния.
