# Making a mergesort visualization

I made a topic earlier about quicksort, now i’m onto mergesort and it’s way harder because of the nature of it’s temporary arrays.
What we were talking about on the other topic ended up becoming this code.
It fails if you try to use B command when it’s already at the start, is screws up the order, but it’s serviceable and o gotta move on to mergesort.
I’m trying some ideas now, i’ll post them soon.

``````import java.lang.*;
int pos = 0;
int dir = 0;
int largura = 20;
//int[] arr = {5,8,15,20,17,14,55,100,11,5,6,67,8,4,12,13,1,47,5,27,38,5,7,50,47,84,9,33,41};
//int[] arr = {60,20,45,100,5,80};
int[] arr;
int[] base;

ArrayList<TrocaPos> solution = new ArrayList<TrocaPos> ();

void setup() {
size(1000, 800);
textSize(16);
textAlign(CENTER, CENTER);
arr = numeros(width /largura, 0, height - 60);
base = numeros(width /largura, 0, height - 60);
arrayCopy(arr, base);
//quickSortIterative(arr, 0, arr.length - 1);
QuickSort(arr, 0, arr.length - 1);
arrayCopy(base, arr);
}

class TrocaPos {
int t0, t1;

TrocaPos(int t0, int t1) {
this.t0 = t0;
this.t1 = t1;
}
}

int[] numeros(int n, int low, int high) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = (int)(low + random(1)*(high-low));
return a;
}

void draw() {
background(250);
fill(0);
text("F = Forward      P = Pause      R = Reverse      V = volta um passo     B = vai um passo", 0, height-60, width, 45);
text(pos, 15,15);
stroke(50, 50, 100);
fill(200, 200, 250);
for (int i = 0; i < arr.length; i++){
rect(i * largura, height-50-arr[i], largura, arr[i]);
}
switch (dir) {
case 1: Forward(); break;
case -1: reverso(); break;
case 2:  if(pos>0){pos--;ForwardStep();}break;
case -2:  if(pos < solution.size()){reversoS();pos++;}break;
}
}

void keyTyped() {
switch(key) {
case 'f': dir = 1; break;
case 'r': dir = -1; break;
case 'p': dir = 0; break;
case 'v': dir = 2; break;
case 'b': dir = -2;  break;
}
}

int corta(int p[], int low, int high){
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

void QuickSort(int arr[], int low, int high)
{
if (low < high) {
int pi = corta(arr, low, high);
QuickSort(arr, low, pi - 1);
QuickSort(arr, pi + 1, high);
}
}

void Forward() {
if (pos < solution.size()) {
TrocaPos sw = solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
pos++;
}
}

void reverso() {
if (pos > 0) {
pos--;
TrocaPos sw =solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
}
}

void ForwardStep() {
if (pos < solution.size()) {
TrocaPos sw = solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
}
dir = 0;
}

void reversoS() {
if (pos > 0) {
TrocaPos sw =solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
}
dir = 0;
}

/*
void quickSortIterative(int arr[], int l, int h)
{
int[] stack = new int[h - l + 1];
int top = -1;

// push initial values of l and h to stack
stack[++top] = l;
stack[++top] = h;

// Keep popping from stack while is not empty
while (top >= 0) {
// Pop h and l
h = stack[top--];
l = stack[top--];

// Set pivot element at its correct larguraition
// in sorted array
int p = corta(arr, l, h);

// If there are elements on left side of pivot,
// then push left side to stack
if (p - 1 > l) {
stack[++top] = l;
stack[++top] = p - 1;
}

// If there are elements on right side of pivot,
// then push right side to stack
if (p + 1 < h) {
stack[++top] = p + 1;
stack[++top] = h;
}
}
}
*/
``````

I was thinking of making an array of arrays (having a hard time of this because i don’t know java) and making the mergesort count how many levels deep he is to control wich array gets filled by each recursion.
I don’t know if it would work but first i gotta figure out how to do it in java

``````import java.lang.*;
int pos = 0;
int dir = 0;
int largura = 20;
int[] arr;
int[] base;

ArrayList<TrocaPos> solution = new ArrayList<TrocaPos> ();
ArrayList<nivelarr> niveis = new ArrayList<nivelarr> ();

void setup() {
size(1000, 800);
textSize(16);
textAlign(CENTER, CENTER);
arr = numeros(width /largura, 0, height - 60);
base = numeros(width /largura, 0, height - 60);
arrayCopy(arr, base);
mergeSort(arr);
criarr(10);
}

void criarr(int n){
for (int i = 0; i < n; i++){
}
}

class nivelarr{
int[] a;
nivelarr(){
this.a = new int[arr.length];

}
}

class TrocaPos {
int t0, t1;

TrocaPos(int t0, int t1) {
this.t0 = t0;
this.t1 = t1;
}
}

int[] numeros(int n, int low, int high) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = (int)(low + random(1)*(high-low));
return a;
}

void draw() {
background(250);
fill(0);
text("F = Forward        P = Pause        R = Reverse", 0, height-60, width, 45);
text(pos, 15,15);
stroke(50, 50, 100);
fill(200, 200, 250);
for (int i = 0; i < arr.length; i++){
rect(i * largura, height-50-arr[i], largura, arr[i]);
}
switch (dir) {
case 1: Forward(); break;
case -1: reverso(); break;
case 2:  if(pos>0){pos--;ForwardStep();}break;
case -2:  if(pos < solution.size()){reversoS();pos++;}break;
}
}

void keyTyped() {
switch(key) {
case 'f': dir = 1; break;
case 'r': dir = -1; break;
case 'p': dir = 0; break;
case 'v': dir = 2; break;
case 'b': dir = -2;  break;
}
}

void Forward() {
if (pos < solution.size()) {
TrocaPos sw = solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
pos++;
}
}

void reverso() {
if (pos > 0) {
pos--;
TrocaPos sw =solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
}
}

void ForwardStep() {
if (pos < solution.size()) {
TrocaPos sw = solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
}
dir = 0;
}

void reversoS() {
if (pos > 0) {
TrocaPos sw =solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
}
dir = 0;
}

void mergeSort(int[] array){
if(array == null)
{
return;
}

if(array.length > 1)
{
int mid = array.length / 2;

// Split left part
int[] left = new int[mid];
for(int i = 0; i < mid; i++)
{
left[i] = array[i];
}

// Split right part
int[] right = new int[array.length - mid];
for(int i = mid; i < array.length; i++)
{
right[i - mid] = array[i];
}
mergeSort(left);
mergeSort(right);

int i = 0;
int j = 0;
int k = 0;

// Merge left and right arrays
while(i < left.length && j < right.length)
{
if(left[i] < right[j])
{
array[k] = left[i];
i++;
}
else
{
array[k] = right[j];
j++;
}
k++;
}
// Collect remaining elements
while(i < left.length)
{
array[k] = left[i];
i++;
k++;
}
while(j < right.length)
{
array[k] = right[j];
j++;
k++;
}
}
}

``````

Now this is some UGLY code! It only works for a set array, it’s the best i could do so far.

``````import java.lang.*;
import java.util.ArrayList;
import java.util.List;
int pos = 0;
int dir = 0;
int largura = 30;
int[] arr = {5,8,15,22,19,16,55,83,11,64,6,67,40,3,12};
int[] base = {5,8,15,20,17,14,55,100,11,5,6,67,8,4,12};
int [] xys ={250,700,  550,700,  240,650,  360,650,  215,600,  250,600,  250 ,550,  285,550,  355,600,  425,600,   355,550,  390,550,  435,550,  470,550,  550,650,  690,650,  550,600,  620,600,    550,550,  585,550,   625,550,   660,550,  695,600,  760,600,   710,550,  745,550,  790,550,  825,550};
int [] xys2 ={250,500,  250,450,  250,450,  250,450, 250,450,360,500,360,500, 430,500, 430,500,360,450,360,450,360,450,360,450,250,400,250,400,250,400,250,400,250,400,250,400,250,400,550,500,550,500, 625,500,625,500,550,450,550,450,550,450,550,450,550,450, 710,500,790,500,790,500,710,450,710,450,710,450,710,450,550,400,550,400,550,400,550,400,550,400,550,400,550,400,550,400,300,350,300,350,300,350,300,350,300,350,300,350,300,350,300,350,300,350,300,350,300,350,300,350,300,350,300,350,300,350};

List<int[]> al = new ArrayList<int[]>();
List<int[]> al2 = new ArrayList<int[]>();

void setup() {
size(1000, 800);
textSize(16);
textAlign(CENTER, CENTER);
//  arr = numeros(15, 0, 100);
arrayCopy(arr, base);
mergeSort(arr);
}

int[] numeros(int n, int low, int high) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = (int)(low + random(1)*(high-low));
return a;
}

void draw() {
background(250);
fill(0);
stroke(50, 50, 100);
fill(200, 200, 250);

int j =0;
int l=0;
for (int i = 0; i < arr.length; i++){
fill(200, 200, 250);
rect( 300+ i * largura, height -50*(j+1), largura, largura);
fill(0);
text(base[i], 300  +largura/2+ i * largura, height -50*(j+1) +largura/2);
}
//text(mouseX, mouseX, mouseY);
for (int[] X : al){
for (int i = 0; i < X.length; i++){
fill(200, 200, 250);
rect( xys[l]+ i * largura, xys[l+1], largura, largura);
fill(0);
text(X[i], xys[l]  +largura/2+ i * largura, xys[l+1] +largura/2);
}
l+=2;
}
l=0;
for (int[] X : al2){
for (int i = 0; i < X.length; i++){
fill(250, 200, 200);
rect( xys2[l]+ i * largura, xys2[l+1], largura, largura);
fill(0);
text(X[i], xys2[l]  +largura/2+ i * largura, xys2[l+1] +largura/2);
}
l+=2;
}

}

void mergeSort(int[] array){
if(array == null)
{
return;
}

if(array.length > 1)
{
int mid = array.length / 2;

int[] left = new int[mid];
int[] leftB = new int[mid];
for(int i = 0; i < mid; i++)
{
left[i] = array[i];
leftB[i] = array[i];
}
int[] right = new int[array.length - mid];
int[] rightB = new int[array.length - mid];
for(int i = mid; i < array.length; i++)
{
right[i - mid] = array[i];
rightB[i - mid] = array[i];
}
mergeSort(left);
mergeSort(right);

int i = 0;
int j = 0;
int k = 0;

while(i < left.length && j < right.length)
{
if(left[i] < right[j])
{
array[k] = left[i];
i++;
}else{
array[k] = right[j];
j++;
}
k++;
}
// Collect remaining elements
while(i < left.length)
{
array[k] = left[i];